Description

难度中等 ：面试题56 - I. 数组中数字出现的次数
一个整型数组 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 <= 10000

    Solution

    第一种思路是：
    将整个数组排序（前提是可以打乱数组的情况），逐个比较，就能够找到两个出现一次的数
    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;
    }
    }
    执行结果：通过
    显示详情：
    执行用时 :8 ms, 在所有 Java 提交中击败了23.93%的用户
    内存消耗 :41.4 MB, 在所有 Java 提交中击败了100.00%的用户
    这种方法会将原数组排好序，移动了原来数组中元素的位置。
    第二种：位运算
    首先简化下问题，如何在一个数组中找到一个只出现一次的数字，其他数字出现两次。
    可以利用异或运算，把数组中的元素全部异或，最后得到的结果就是只出现一次的数字。这是因为如果两个数字相同，那么异或的结果就 0， 多个只出现两次的数字异或就等于0。所以数组中全部异或的结果就是只出现一次的那个数。
    题目的要求是，找到两个只出现一次的数字，设其中一位为 a， 另一个为 b
    数组中全部元素异或的结果，就是两个只出现一次的数字异或的结果（a ^ b）。
    在 a ^ b 的二进制位中，如果二进制位中有一位为 0， 则表示 a 与 b 在这一位上是相同的，如果有一位为 1，则表示在这一位上 a， b 是不同的。
    所以可以找到 a ^ b 的二进制中上这一位等于1，即 a 与 b 在这一位上是不同的，以此来在数组中找到 a， b 这两个数。记为 div
    而相同数字在这一位上是相同的，所以也可以将相同元素分到一起异或，也就是异或为0。最后就可以在数组中找到 a, b 两个元素。
    class Solution {
    public int[] singleNumbers(int[] nums) {
    int result = 0;
    for(int n : nums)
    result ^= n; // 此时 result == a ^ b
    int div = 1; // 记录 result 中某一位等于 1 的位
    while((div & result) == 0) // 与 result 进行逐位异或，找到 result 中某一位等于1的位。
    div <<= 1;
    int a = 0, b = 0;
    for(int n: nums){
    if((div & n) == 0 )
    a ^= n;
    else
    b ^= n;
    }

    int[] res = {a,b};
    return res;
    }
    }