LeetCode137-只出现一次的数字II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/single-number-ii/

中文链接：https://leetcode-cn.com/problems/single-number-ii/

题目详述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,3,2]
输出: 3

示例 2:

1
2
输入: [0,1,0,1,0,1,99]
输出: 99

题目详解

  • 本题是 LeetCode136-只出现一次的数字 的进阶版，除了某个元素只出现一次以外，其余每个元素从均出现两次变为了均出现了三次。
  • 当元素出现次数上升到出现 3 次及 3 次以上时，就无法简单地运用异或来进行解答，但同样都是运用位运算的一些基本操作。
  • 下面给出两种解答方法，它们的通解可以解答除了某个元素只出现 m 次以外，其余每个元素均出现 k（k > m）次的问题。

方法一：统计每一位 1 的个数，并对 3 取模。

  • 对 int 型整数的 32 位，分别统计每一位上 1 的个数，并对 3 取模。
  • 这样，出现三次的数的二进制位上的 1 会全部消掉，1 全部来源于只出现一次的数，所有二进制位的 1 对应只出现一次的数的二级制位的 1。
  • 最终这个数就是只出现一次的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode_00137 {

    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int t = 0;
            for (int num : nums) {
                t += (num >> i) & 1;
            }
            res |= (t % 3) << i;
        }
        return res;
    }
}

通解为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode_00137 {

    public int singleNumber(int[] nums, int m, int k) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int t = 0;
            for (int num : nums) {
                t += (num >> i) & 1;
            }
            res |= (t % k / m) << i;
        }
        return res;
    }
}

方法二：状态机法，用 2 个数表示状态机的 3 个状态。

  • 用 3 个状态表示对于某个数字出现了多少次：00、01、10、00。也就是累加的过程 0 -> 1 -> 2 -> 0，当达到 3 时记为 0。
  • 所以我们可以用两个 int 型整数来表示所有数中每一位出现 1 的次数。用 ones 表示状态中的倒数第一位，用 twos 表示倒数第二位。如：ones 的第 3 位为 0，twos 的第3位为 1，则表示当前累计的所有元素中，各个元素的第 3 位上出现 1 的个数为 2 个。
  • 根据：
    • 00 + 1 = 01
    • 01 + 1 = 10
    • 10 + 1 = 00（mod 3）
  • 那么对于状态 twos ones，得到新状态的算法如下：
    • ones = (ones ^ r) & ~twos
    • twos = (twos ^ r) & ~ones
  • 因为我们最后要求的是只出现 1 次的元素，所以经过操作后，32 个 位上出现 1 只有一次的元素就是我们要返回的元素，也就是ones当前保存的元素。
1
2
3
4
5
6
7
8
9
10
11
public class LeetCode_00137 {

    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}

通解为：

  • 用 k - 1 个数分别表示状态机的 k 个状态。
  • 最后 bits[m - 1] 就是结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00137 {

    public int singleNumber(int[] nums) {
        return singleNumber(nums, 3);
    }

    private int singleNumber(int[] nums, int k) {
        int[] bits = new int[--k];
        for (int num : nums) {
            for (int i = 0; i < k; i++) {
                int mask = -1;
                for (int j = 0; j < k; j++) {
                    if (i != j) {
                        mask &= ~bits[j];
                    }
                }
                bits[i] = (bits[i] ^ num) & mask;
            }
        }
        return bits[0];
    }
}