LeetCode 645. Set Mismatch

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), prev = 0;
        vector<int> ans(2);
        for (int num : nums) {
            if (num == prev) {
                ans[0] = num;
            } else if (num - prev > 1) {
                ans[1] = prev + 1;
            }
            prev = num;
        }
        if (nums.back() != n) ans[1] = n;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 10001;
int c[N];
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        memset(c, 0, (n + 1) * 4);
        vector<int> ans(2);
        for (int num : nums)
            if (++c[num] == 2)
                ans[0] = num;
        for (int i = 1; i <= n; ++i)
            if (c[i] == 0) {
                ans[1] = i;
                break;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size(), mask = 0, i = 0;
        while (++i <= n) mask ^= i;
        for (int num : nums) mask ^= num;
        i = 0, mask = mask & (-mask); // lowbit.
        int num1 = 0, num2 = 0;
        while (++i <= n) {
            if ((i & mask) == 0) num1 ^= i;
            else num2 ^= i;
        }
        for (int num : nums) {
            if ((num & mask) == 0) num1 ^= num;
            else num2 ^= num;
        }
        for (int num : nums) {
            if (num == num1)
                return {num1, num2};
            if (num == num2)
                return {num2, num1};
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size(), idx;
        for (int i = 0; i < n; ++i) {
            idx = (nums[i] - 1) % n;
            nums[idx] += n;
        }
        vector<int> ans(2);
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 2 * n)
                ans[0] = i + 1;
            else if (nums[i] <= n)
                ans[1] = i + 1;
        }
        return ans;
    }
};