题目

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

思路

  • 先进行异或操作，可以获得这两个数的异或即a ^ b
  • 其中a ^ b因为a与b不同则必不为0
  • 我们找到 其二进制串中为1的位置将数组分为两组，一组这位的数为0，一组这位的数为1
  • 那么只出现了一次的数字将会被分到不同组中，且组中其他的数字是两两相同的，所以再进行异或操作，可以分别获得这两个数字的值

    代码

    1. class Solution {
    2.   public int[] singleNumbers(int[] nums) {
    3.       int res = 0;
    4.       for (int num : nums) {
    5.           res ^= num;
    6.       }
    7.       int index = 0;
    8.       while (res != 0) {
    9.           if (((res >> index) & 1) == 1) {
    10.               break;
    11.           }
    12.           index++;
    13.       }
    14.       int res1 = 0;
    15.       int res2 = 0;
    16.       for (int num : nums) {
    17.           if (((num >> index) & 1) == 1) {
    18.               res1 ^= num;
    19.           } else {
    20.               res2 ^= num;
    21.           }
    22.       }
    23.       int[] result = new int[]{res1, res2};
    24.       return result;
    25.   }
    26. }