# Set Mismatch

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

> The set`S`originally contains numbers from 1 to`n`. But unfortunately, due to the data error, one of the numbers in the set got duplicated to**another**number in the set, which results in repetition of one number and loss of another number.
>
> Given an array`nums`representing 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/bit-manipulation/xor/set-mismatch.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.