题目

原题在此

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:
Input: nums = [1,2,2,4]
Output: [2,3]

Example 2:
Input: nums = [1,1]
Output: [1,2]

Constraints:

2 <= nums.length <= $10^4$
1 <= nums[i] <= $10^4$

解析

根据题意,要返回一个长度为2的数组, 其中res[0]为重复出现的值, res[1]为缺少的值.
对于任意整数i, 有 i ^ i == 0 => 1^2^3^4 ^ 1^2^3^4 == 0 => 1^2^3^4 ^ 1^2^2^4 == 2 ^ 3, 将异或结果暂存在res[1];
统计每个元素的出现次数, 将出现两次的数记录在res[0], 此时res[1] = res[1] ^ res[0].

代码

c++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        vector<int> count(n);
        vector<int> res = {0, 0};
        for(int i = 0; i < n; ++i) {
            res[1] ^= nums[i] ^ (i+1);
            if(++count[nums[i]-1] == 2) res[0] = nums[i];
        }
        res[1] ^= res[0];
        return res;
    }
};