Ex56-I 数组中数字出现的次数

题目描述

一个整型数组 nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

解题思路

解题步骤如下：

• 将所有的数字异或起来，得到一个res；
• 得到的res，其每个为1的位代表了要求的两个数（num1，num2）在这一位上不同，不妨就用这个数的第一个为1的位，得到index；
• 把所有的数分为两组，一个组上index为为1，其中比包含2m+1个数字，其中多处来的一个数字，就是要求的两个数字中的一个数字；另一半会有2n+1个数字，多处来的一个数字就是要求的两个数字中的另一个数字；
• 所以，在这个基础上对两组数据进行异或，得到的就是要求的两个数字。

备注：

• 上面说的位都是二进制位；
• 上面说的“把所有的数分为两组”这个过程不是真实进行的。

代码

class Solution {
 public:
  std::vector<int> singleNumbers(std::vector<int>& nums) {
    decltype(nums.size()) nums_size = nums.size();
    if (nums_size < 2) return nums;
    auto xor_res = nums[0];
    for (decltype(nums.size()) i = 1; i < nums_size; ++i) {
      xor_res ^= nums[i];
    }
    auto index_first_bit_1 = find_first_bit_1(xor_res);
    int num1 = 0, num2 = 0;
    for (decltype(nums.size()) i = 0; i < nums_size; ++i) {
      if (is_bit_1(nums[i], index_first_bit_1))
        num1 ^= nums[i];
      else
        num2 ^= nums[i];
    }
    std::vector<int> res = {num1, num2};
    return res;
  }

 private:
  int find_first_bit_1(int num) {
    int index_bit = 0;
    while ((num & 1) == 0 && index_bit < 8 * sizeof(int)) {
      num = num >> 1;
      ++index_bit;
    }
    return index_bit;
  }

  bool is_bit_1(int num, int index) {
    num = num >> index;
    return num & 1;
  }
};

结果

执行结果：通过

执行用时：36 ms, 在所有 C++ 提交中击败了92.02%的用户

内存消耗：16 MB, 在所有 C++ 提交中击败了60.21%的用户