剑指 Offer 56 - I. 数组中数字出现的次数

解题思路：位运算

本题给定的数组 nums 中，只有两个出现过一次的数字，其余数字均出现两次

如果本题给定的条件是，数组 nums 中，只有一个数字出现过一次，其余数字均出现过两次，你会如何求解呢？

其实非常简单，我们只需要将所有数字都异或起来，最后的结果就是那个只出现过一次的数字。

异或（XOR）运算的性质：

  • 相同数字异或结果为 0

  • 0 与任何数异或的结果都是这个数字本身

  • 异或运算满足交换律和结合律：

    • a ^ b = b ^ a

    • (a ^ b) ^ c = a ^ (b ^ c)

如果像处理只出现过一次的数字那样，将数组中所有的数字全部异或起来，我们得到的结果为两个只出现一次的数字异或起来的结果。

假设两个均出现一次的数字分别为 a 和 b

我们将所有数字异或起来的结果为 xor，xor = a ^ b

因为 a != b ，所以 xor != 0

思路：巧用 n & (~n + 1)

找到 xor 最右边的那个 1 代表的数，因为 xor != 0，所以我们必然可以找到 xor 最右边的那个 1

那么如何找到 xor 最右边的 1 呢？

先上结论：

  1. int rightOne = num & (~num + 1);

这是一个在位运算题目中常用的技巧

来看示例：

num = 10101000; 我们知道 num 最右边的那个 1 代表数为 00001000

  1. ~num = 01010111
  2. ~num + 1 = 01011000
  3. num & (~num + 1) = 00001000

通过示例，不难思考这个过程；num & (~num + 1) 即可以找到 num 最右的 1 代表的数

找到这个数以后，我们再次遍历整个数组，如果 num & rightOne == rightOne ，我们就将数字异或起来，这样我们得到的异或出来的结果就是这两个只出现过一次的数字中的一个 , 将该结果赋值给 a

然后我们再用 xor ^ a ，就可以得到另外一个只出现过一次的数字 b 了

代码

  1. class Solution {
  2.     public int[] singleNumbers(int[] nums) {
  3.         int xor = 0;
  4.         for(int num : nums){
  5.             xor ^= num;
  6.         }
  7.         int a = 0;
  8.         int b = 0;
  9.         int rightOne = xor & (~xor + 1);
  10.         for(int num : nums){
  11.             if((num & rightOne) == rightOne){
  12.                 a ^= num;
  13.             }
  14.         }
  15.         b = xor ^ a;
  16.         return new int[]{a,b};
  17.     }
  18. }

复杂度分析

  • 时间复杂度：O(N)

遍历了两次数组，所以该算法的时间复杂度为：O(N)

  • 空间复杂度：O(1)

我们仅用到有限的几个变量，空间复杂度为 O(1)