数组数字出现次数问题

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

1
2
Input: nums = [2,2,1]
Output: 1

Example 2:

1
2
Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

1
2
Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

位运算

用异或操作抵消相同的数字

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}

Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

1
2
Input: nums = [2,2,3,2]
Output: 3

Example 2:

1
2
Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each element in nums appears exactly three times except for one element which appears once.

位运算

同样是位运算，但由于这里需要抵消出现三次的数字，所以需要对每一位bit，出现次数mod 3，
这样就可以消除出现三次的数字。

实际上，上一题的异或操作的就是mod 2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += num >> i & 1;
            }
            res |= cnt % 3 << i;
        }
        return res;
    }
}

Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

1
2
3
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

1
2
Input: nums = [-1,0]
Output: [-1,0]

Example 3:

1
2
Input: nums = [0,1]
Output: [1,0]

Constraints:

  • 2 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

位运算+脑筋急转弯

这里要找出两个只出现一次的数字，所以异或操作后的结果是这两个数字的异或xor，
我们只需要找到其中一个数字，就相当于找到了两个数字（可以通过异或得到）。
那么如何找到一个数字呢，这里需要一个技巧。我们知道，对于这个结果xor（这个
32位的bit），考虑其中的某一位值为1的bit（不妨考虑最低位的值为1的bit），
这个值为1的bit肯定是来自两个数字中的某一个，于是我们可以通过异或数组中所有
这个bit值为1的数字求得其中一个我们想要的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] singleNumber(int[] nums) {
      int res[] = new int[2], xor = 0;
      for (int num : nums) {
        xor ^= num;
      }
      int rightOneBit = xor & (~xor + 1);
      for (int num : nums) {
        if ((num & rightOneBit) > 0) {
          res[0] ^= num;
        }
      }
      res[1] = res[0] ^ xor;
      return res;
    }
}