Set Mismatch – Find the Duplicate and Missing Number in Array


Given an array of integers of size N. The array should originally store numbers from 1 to N, however, during transmission, one of the number is duplicated to another number due to data error – this results in one number duplicated and one number missing.

Write a C/C++ function to find the duplicate and missing number in an array – return them in the form of an array.
For example: Input: nums = [1,2,2,4] and the Output: [2,3]

Sorting

Sorting takes O(N LogN) complexity and when can go through the array in O(N) for duplicated number and missing number.

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) {
        vector<int> data = {-1, 1};
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i - 1] == nums[i]) {
                data[0] = nums[i - 1];
            } else if (nums[i] > nums[i - 1] + 1) {
                data[1] = nums[i - 1] + 1;
            }
        }
        if (nums[nums.size() - 1] != nums.size()) {
            data[1] = nums.size();
        }
        return data;
    }
};
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> data = {-1, 1};
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i - 1] == nums[i]) {
                data[0] = nums[i - 1];
            } else if (nums[i] > nums[i - 1] + 1) {
                data[1] = nums[i - 1] + 1;
            }
        }
        if (nums[nums.size() - 1] != nums.size()) {
            data[1] = nums.size();
        }
        return data;
    }
};

If the last number in the sorted array is not the N (size of the array), the missing number can be simply set to N. This approach uses O(1) constant space.

Set

It is straightforward to use set (or preferably the unordered_set). The space complexity is O(N) and the time complexity is also O(N). We push the number to the set if it is not included and otherwise, we find the duplicate number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_set<int> data;
        vector<int> result = {0, 0};
        for (const auto &n: nums) {
            if (data.count(n)) {
                result[0] = n;
            } else {
                data.insert(n);
            }
        }
        for (int i = 1; i <= nums.size(); ++ i) {
            if (data.count(i) == 0) {
                result[1] = i;
                break;
            }
        }
        return result;
    }
};
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_set<int> data;
        vector<int> result = {0, 0};
        for (const auto &n: nums) {
            if (data.count(n)) {
                result[0] = n;
            } else {
                data.insert(n);
            }
        }
        for (int i = 1; i <= nums.size(); ++ i) {
            if (data.count(i) == 0) {
                result[1] = i;
                break;
            }
        }
        return result;
    }
};

The second O(N) loop will check for missing number that it is not in the set.

Flag

The original numbers are from 1 to N and thus we can negate them the first time they are met. If a number is already marked – we find the duplicate number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> data = {-1, -1};
        for (int i = 0; i < nums.size(); ++ i) {
            int n = abs(nums[i]);
            if (nums[n - 1] < 0) {
                data[0] = n;
            } else {
                nums[n - 1] *= -1;
            }
        }
        for (int i = 0; i < nums.size(); ++ i) {
            if (nums[i] > 0) {
                data[1] = i + 1;
            }
        }        
        return data;
    }
};
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> data = {-1, -1};
        for (int i = 0; i < nums.size(); ++ i) {
            int n = abs(nums[i]);
            if (nums[n - 1] < 0) {
                data[0] = n;
            } else {
                nums[n - 1] *= -1;
            }
        }
        for (int i = 0; i < nums.size(); ++ i) {
            if (nums[i] > 0) {
                data[1] = i + 1;
            }
        }        
        return data;
    }
};

The second loop will look for missing number – the one which is still positive (not marked yet). O(1) space complexity and O(N) time complexity.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
507 words
Last Post: Embracing HF20! My Steem Witness Node Upgraded to v0.20.2 on a new Server!
Next Post: Algorithms to Check If Any Two Intervals Overlap

The Permanent URL is: Set Mismatch – Find the Duplicate and Missing Number in Array

Leave a Reply