错误的集合

[xiwenAndlejian]

leetcode

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:

输入: nums = [1,2,2,4]
输出: [2,3]

注意:

1. 给定数组的长度范围是 [2, 10000]。
2. 给定的数组是无序的。

解法

分析

我们需要获取集合复制错误后，丢失的一个元素(a)以及重复的一个元素(b)。

集合S= [1, 2, 3, ... b, b, ... n]

而正确的集合 = [1, 2, 3, ... a, b, ... n]

从落单的数里面我们已经知道

1. a^a=0
2. a^a^b=a^b^a=b

因此，我们不妨将S和正确的集合中的所有元素互做异或，不难得出所得结果为X=a^b。

只要我们获得了a、b两者中一个的值，即可与X异或求得另一个的值。

由于数组是无序的，无法用龟兔竞走的方式来求得重复的节点。

但是数组长度(n)是固定的，且范围[1, n]。因此可以创建一个数组，将S的元素进行排序，求得重复的元素b。

解：异或

1. 排序求得重复数a
2. 通过异或S以及正确集合中的所有元素，求得异或结果X=a^b
3. 再通过a^X = a^a^b =b求得b

public int[] findErrorNums(int[] nums) {
    boolean[] temp = new boolean[nums.length + 1];
    int t = 0;
    for (int i = 0; i < nums.length; i++) {
        if (temp[nums[i]]) {
            t = nums[i];
            break;
        }
        temp[nums[i]] = true;
    }
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        result = result ^ (i + 1) ^ nums[i];
    }
    return new int[]{t, result ^ t};  
}