Simple C++ solution with explanation, O(n) time with in-place operation


  • 0

    First of all, this problem is not 'medium' enough ;-) The key condition '1 <= a[I] <= n, n = a.size()' implies too many things. Here is my explanation in brief:

    Considering the condition, if there is no duplication, the numbers in the array should be 1, 2, 3, ..., n. These are all the numbers, though they could be in any order.

    If they are sorted, the array should be like: a[1] = 1, a[2] = 2, a[3] = 3, ..., a[n] = n. We can sort the disordered input array in the following way: (it is O(n))

    1. Go through the items one by one;
    2. If the current item equals to the current index, skip to the next;
    3. If the current item doesn't equal to the current index, swap.
      suppose a[3] = 7, swap a[3] with a[7]. Now a[7] has 'correct' number 7, but a[3] might still have 'wrong' number. No worries, do 2) -> 3) again until a[3] has 'correct' number, then we step to a[4] according to 2)'s rule.

    If there is no duplication, after this O(n) iteration, the array is sorted as each item equals to its index. But if we have duplication, when doing swap in step 3), we will have two identical number waiting to be swapped, thus we found one pair of duplicated numbers.

    class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
            
            vector<int> r;
    
            for(size_t i = 1; i <= nums.size();) {
                
                // i starts from 1 while index from 0, so we use i - 1
                int &r1 = nums[i - 1];
                
                // do step 2)'s check
                if(i == r1) {
                    i++; // skip to the next
                }
                else {
                    int &r2 = nums[r1 - 1];
                    
                    // found two identical numbers to be swapped
                    if(r1 == r2) {
                        r.push_back(r1);
                        r1 = 0; // eliminate one or we may output it multiple times
                        i++;
                    }
                    // do step 3)'s swap
                    else if( /*r1 != r2 &&*/ 0 != r2) {
                        r1 ^= r2;
                        r2 ^= r1;
                        r1 ^= r2;
                    }
                    else  /*(r1 != r2 && 0 == r2)*/ {
                        // just move the current item to where it should be at
                        r2 = r1;
                        r1 = 0;
                        i++;
                    }
                }
            }
            
            return r;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.