2021/3/16 数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例

输入

[1,4,1,6]

返回值

[4,6]

说明

返回的结果中较小的数排在前面

解题思路

1. 先使用 Set 集合存储数字，如果出现了第二个相同的数字，会在 Set 中找到对应的值，此时再将 Set 里的这个值删除。最后剩下的就是只出现过一次的数字了。我这里用的是 Java 中的 TreeSet，可以满足排序的需求。
2. 对数组中所有的数进行异或运算，最终结果会得到两个不同数值的异或结果
   
   如上面例子中的数组，做一次异或运算，最后 1 会被消去，只剩下 4 和 6 的异或结果 xor。
   然后我们再找这个 xor 的最后一个 1 的位置，
   
   因为有两个数是不重复的，所以最后一个 1 的位置说明这两个数在这个位置上的二进制，其中一个是 1，另一个是 0，我们可以根据这个特性给它们分别存放在容量为 2 的数组的不同的位置中。得到最后的 1 这个数字之后，用这个数再次与整个数组进行异或运算，重复的数会被消去，只剩下那个唯一的值。最终得出结果。

Java代码实现

1. 集合存储法

import java.util.*;
public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        // Lambda 表达式定义排序规则，小的在前，大的在后
        TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o1 - o2);
        int[] res = new int[2];
        for (int i = 0; i < array.length; ++i) {
            if (set.contains(array[i])) {    // 如果 Set 中有这个值，说明重复了 
                set.remove(array[i]);    // 因题目只考虑 2 次，所以直接删除即可
            } else {
                set.add(array[i]);    // 若第一次出现，加入集合中
            }
        }
        int index = 0;
        for (Integer i : set) {
            res[index++] = i;
        }
        return res;
    }
}

2. 位运算法

import java.util.*;


public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        int xor = array[0];
        for (int i = 1; i < array.length; ++i) {
            xor ^= array[i];
        }
        // 寻找二进制中最右边的 1
        xor -= xor & (xor - 1);
        int[] res = new int[2];
        for (int i = 0; i < array.length; ++i) {
            // 根据他们是 1 还是 0，来分配在数组 res 中的位置
            if ((xor & array[i]) == 0) res[0] ^= array[i];
            else res[1] ^= array[i];
        }
        // 排序
        if (res[0] > res[1]) {
            int temp = res[0];
            res[0] = res[1];
            res[1] = temp;
        }
        return res;
    }
}