Description

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

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

  • 2 <= nums.length <= 10000

Solution

位运算，所有数进行异或，异或后的结果为所查找的两个数的异或，找到两个数异或后的结果中，位数为 1 的数，即可区分出这两个数。

  1. class Solution {
  2.     public int[] singleNumbers(int[] nums) {
  3.         int allXor = 0;  
  4.         // 所有数进行异或，最后结果为所查找的两个数的异或
  5.         for (int num : nums){
  6.             allXor ^= num;
  7.         }
  8.         // 找到 allXor 右边第一个 1， 即为所要找的两个数中区别位
  9.         int digit = 1;
  10.         while(( digit & allXor ) == 0){
  11.             digit <<= 1;
  12.         }   
  13.         // 找出两个不同的数
  14.         int a = 0, b = 0;
  15.         for (int num : nums){
  16.             if ((num & digit) != 0)  // num & digit 的结果为 不等于 0 或者 等于 0
  17.                 a ^= num;
  18.             else 
  19.                 b ^= num;
  20.         }
  21.         return new int[]{a, b};
  22.     }
  23. }

执行结果：通过
显示详情
执行用时：2 ms, 在所有 Java 提交中击败了87.89%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了73.83%的用户

排序再比较查找

class Solution {
    public int[] singleNumbers(int[] nums) {
        Arrays.sort(nums);   
        int[] result = new int[2];     
        int i = 0, index = 0;
        while(i < nums.length){
            int temp = i + 1;
            while(temp < nums.length && nums[temp] == nums[i])
                temp ++;
            if(i+1 == temp)
                result[index++] = nums[i];
            i = temp;
        }

        return result;
    }
}