LeetCode-645. Set Mismatch [C++][Java]

LeetCode-645. Set Mismatch [C++][Java] LeetCode-645. Set Mismatchhttps://leetcode.com/problems/set-mismatch/题目描述

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 <= 1041 <= nums[i] <= 104

解思路

【C++解法】

1. Brute Force

Time complexity : O(n^2). We traverse over the numsnums array of size n for each of the numbers from 1 to n.

Space complexity : O(1). Constant extra space is used.

The most naive solution is to consider each number from 1 to n, and traverse over the whole numsnums array to check if the current number occurs twice in numsnums or doesn't occur at all. We need to set the duplicate number, dupdup and the missing number, missingmissing, appropriately in such cases respectively.

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

2. Using Sorting

Time complexity : O(nlogn). Sorting takes O(nlogn) time.

Space complexity : O(logn). Sorting takes O(logn) space.

One way to further optimize the last approach is to sort the given numsnums array. This way, the numbers which are equal will always lie together. Further, we can easily identify the missing number by checking if every two consecutive elements in the sorted numsnums array are just one count apart or not.

class Solution {
public:
    vector findErrorNums(vector& nums) {
        int dup = -1, miss = 1;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {dup = nums[i];}
            else if (nums[i] > nums[i - 1] + 1) {miss = nums[i - 1] + 1;}
        }
        if (nums[nums.size() - 1] != nums.size()) {miss = nums.size();}
        return vector {dup, miss};
    }
};

3. Using Map

Time complexity : O(n). Traversing over numsnums of size nn takes O(n) time. Considering each number from 1 to n also takes O(n) time.

Space complexity : O(n). mapmap can contain atmost nn entries for each of the numbers from 1 to n.

The given problem can also be solved easily if we can somehow keep a track of the number of times each element of the numsnums array occurs. One way to do so is to make an entry for each element of numsnums in a HashMap mapmap. This mapmap stores the entries in the form (num_i, count_i)(numi​,counti​). Here, numnum refers to the i^{th}ith element in numsnums and count_icounti​ refers to the number of times this element occurs in numsnums. Whenever, the same element occurs again, we can increment the count corresponding to the same.

After this, we can consider every number from 11 to nn, and check for its presence in mapmap. If it isn't present, we can update the missingmissing variable appropriately. But, if the countcount corresponding to the current number is 22, we can update the dupdup variable with the current number.

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

4. Using Constant Space

We can save the space used in the last approach, if we can somehow, include the information regarding the duplicacy of an element or absence of an element in the numsnums array. Let's see how this can be done.

We know that all the elements in the given numsnums array are positive, and lie in the range 1 to n only. Thus, we can pick up each element ii from numsnums. For every number i picked up, we can invert the element at the index ∣i∣. By doing so, if one of the elements j occurs twice, when this number is encountered the second time, the element nums[∣i∣] will be found to be negative. Thus, while doing the inversions, we can check if a number found is already negative, to find the duplicate number.

After the inversions have been done, if all the elements in numsnums are present correctly, the resultant numsnums array will have all the elements as negative now. But, if one of the numbers, j is missing, the element at the  index will be positive. This can be used to determine the missing number.

class Solution {
public:
    vector findErrorNums(vector& nums) {
        int dup = -1, miss = 1;
        for (int n : nums) {
            if (nums[abs(n) - 1] < 0) {dup = abs(n);}
            else {nums[abs(n) - 1] *= -1;}
        }
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > 0) {miss = i + 1;}
        }
        return vector {dup, miss};
    }
};

5. Using XOR

Time complexity : O(n) We iterate over nn elements five times.

Space complexity : O(1). Constant extra space is used.

Before we dive into the solution to this problem, let's consider a simple problem. Consider an array with n-1 elements containing numbers from 1 to n with one number missing out of them. Now, how to we find out this missing element. One of the solutions is to take the XOR of all the elements of this array with all the numbers from 1 to n. By doing so, we get the required missing number. This works because XORing a number with itself results in a 0 result. Thus, only the number which is missing can't get cancelled with this XORing.

Now, using this idea as the base, let's take it a step forward and use it for the current problem. By taking the XOR of all the elements of the given nums array with all the numbers from 1 to n, we will get a result, xor, as x^y. Here, x and y refer to the repeated and the missing term in the given nums array. This happens on the same grounds as in the first problem discussed above.

Now, in the resultant xor, we'll get a 1 in the binary representation only at those bit positions which have a 1 in one out of the numbers x and y, and a 0 at the same bit position in the other one. In the current solution, we consider the rightmost bit which is 1 in the xor, although any bit would work. Let's say, this position is called the rightmostbit.

If we divide the elements of the given nums array into two parts such that the first set contains the elements which have a 1 at the rightmostbit position and the second set contains the elements having a 0 at the same position, we'll get one out of x or y in one set and the other one in the second set. Now, our problem has reduced somewhat to the simple problem discussed above.

To solve this reduced problem, we can find out the elements from 1 to n and consider them as a part of the previous sets only, with the allocation of the set depending on a 1 or 0 at the righmostbit position.

Now, if we do the XOR of all the elements of the first set, all the elements will result in an XOR of 0, due to cancellation of the similar terms in both nums and the numbers (1:n), except one term, which is either x or y.

For the other term, we can do the XOR of all the elements in the second set as well.

Consider the example [1 2 4 4 5 6]

One more traversal over the numsnums can be used to identify the missing and the repeated number out of the two numbers found.

class Solution {
public:
    vector findErrorNums(vector& nums) {
        int tmp = 0, xor0 = 0, xor1 = 0;
        for (int n: nums) {tmp ^= n;}
        for (int i = 1; i <= nums.size(); i++) {tmp ^= i;}
        int rightmostbit = tmp & ~(tmp - 1);
        for (int n: nums) {
            if ((n & rightmostbit) != 0) {xor1 ^= n;}
            else {xor0 ^= n;}
        }
        for (int i = 1; i <= nums.size(); i++) {
            if ((i & rightmostbit) != 0) {xor1 ^= i;}
            else {xor0 ^= i;}
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == xor0) {return vector {xor0, xor1};}
        }
        return vector {xor1, xor0};
    }
};

6. Swap

class Solution {
public:
    vector findErrorNums(vector& nums) {
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i + 1) {
                return vector {nums[i], i + 1};
            }
        }
        return vector {};
    }
    void swap(vector& nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

7. Brute Froce with extra space

class Solution {
public:
    vector findErrorNums(vector& nums) {
        int size = nums.size();
        vector v(size + 1);
        vector result;
        for(auto i : nums) {
            if(v[i] >= 1) result.push_back(i);
            v[i]++;
        }
        for(int i = 1; i < v.size(); ++i) {
            if(v[i] == 0)  result.push_back(i);
        }
        return result;
    }
};

【Java解法】 1. Brute Force

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int dup = -1, missing = -1;;
        for (int i = 1; i <= nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == i)
                    count++;
            }
            if (count == 2)
                dup = i;
            else if (count == 0)
                missing = i;
            if (dup > 0 && missing > 0)
                break;
        }
        return new int[] {dup, missing};
    }
}

2. Using Sorting

public class Solution {
    public int[] findErrorNums(int[] nums) {
        Arrays.sort(nums);
        int dup = -1, missing = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1])
                dup = nums[i];
            else if (nums[i] > nums[i - 1] + 1)
                missing = nums[i - 1] + 1;
        }
        return new int[] {dup, nums[nums.length - 1] != nums.length ? nums.length : missing};
    }
}

3. Using Map

public class Solution {
    public int[] findErrorNums(int[] nums) {
        Map < Integer, Integer > map = new HashMap();
        int dup = -1, missing = 1;
        for (int n: nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (map.containsKey(i)) {
                if (map.get(i) == 2)
                    dup = i;
            } else
                missing = i;
        }
        return new int[]{dup, missing};
    }
}

4. Using Extra Array

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] arr = new int[nums.length + 1];
        int dup = -1, missing = 1;
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]] += 1;
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == 0)
                missing = i;
            else if (arr[i] == 2)
                dup = i;
        }
        return new int[]{dup, missing};
    }
}

5. Using Constant Space

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int dup = -1, missing = 1;
        for (int n: nums) {
            if (nums[Math.abs(n) - 1] < 0)
                dup = Math.abs(n);
            else
                nums[Math.abs(n) - 1] *= -1;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > 0)
                missing = i + 1;
        }
        return new int[]{dup, missing};
    }
}

6. Using XOR

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int xor = 0, xor0 = 0, xor1 = 0;
        for (int n: nums)
            xor ^= n;
        for (int i = 1; i <= nums.length; i++)
            xor ^= i;
        int rightmostbit = xor & ~(xor - 1);
        for (int n: nums) {
            if ((n & rightmostbit) != 0)
                xor1 ^= n;
            else
                xor0 ^= n;
        }
        for (int i = 1; i <= nums.length; i++) {
            if ((i & rightmostbit) != 0)
                xor1 ^= i;
            else
                xor0 ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == xor0)
                return new int[]{xor0, xor1};
        }
        return new int[]{xor1, xor0};
    }
}

参考文献

【1】n&(n-1)表示什么？n&(-n)表示什么？_XZY028的博客-CSDN博客_n表示什么

【2】位运算n-n&(~n+1)表示的是什么_百度知道

【3】n&(n-1)位运算的妙用 - 小时候挺菜 - 博客园