Set Mismatch

https://leetcode.com/problems/set-mismatch/description/

The setSoriginally contains numbers from 1 ton. But unfortunately, due to the data error, one of the numbers in the set got duplicated toanothernumber in the set, which results in repetition of one number and loss of another number.

Given an arraynumsrepresenting the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Thoughts

因为是1,.i,i.,n，我们可以让它们XOR 1,...n, 得到a ^ b ^ b ^ b = a ^ b = res. 我们再找出现过两次的b然后用res ^ b = a得到a.

Code

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] count = new int[nums.length];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
            res ^= i + 1;
            count[nums[i] - 1]++;
        }

        int[] ans = new int[2];

        for (int i = 0; i < count.length; i++) {
            if (count[i] == 2) {
                ans[0] = i + 1;
            }
        }

        ans[1] = ans[0] ^ res;
        return ans;
    }
}

时间复杂度O(n), 空间O(n).

Ver 2

如果排好了序那就好做多了。一种是调用sorting算法，但由于我们已经知道了里头元素是1到n，那我们可以直接把它们值和index对应起来：把nums[i]放到nums[i-1](第nums[i]个位置), i位置应该放i + 1（即nums[i] == i + 1）。

class Solution {
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public int[] findErrorNums(int[] nums) {
        int[] ans = new int[2];

        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1); // 避开环， 当nums[i] == nums[nums[i] - 1]时 
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] - 1 != i) {
                ans[0] = nums[i];
                ans[1] = i + 1;
                break;
            }
        }

        return ans;
    }
}

时间O(n), 空间O(1).