3 Accepted Solutions: bit-wise inverse, swap, and cheat(using O(n) space)


  • 1

    The cheating one is the most straight forward; I tested it just to see if the problem's author meant to allow the additional space usage; And the answer is (currently?) yes, if the author is not mistaking. It is accepted even when using integer vector as presentation records.

    Okay, let's talk about the real one:

    1. the first one is recording if a number is presented in the array or not. Taking advantage of the problem input constraint, there are only positive integers. When a number is inverted at bit-level, we can tell the original number as well as if the number is inverted. Some other reversible operations can be used as well: simple negation, or add the array size. I like bitwise inverse because it is the simplest one in terms of implementation effort and hardware complexity. Oh, and inverse has the highest flexibility: negation only covers "positive" integers" instead of "non-negative" ones, and size offest needs to handle overflow issue carefully.

    2. Swap-based approach is to put number 'x' into position 'x-1'. When there is a collision, then we know the number is repeated. (I like to make my thinking clean and I make the position shift outside the loop (see declaration of 'int* arr'), so you won't see that coming in the loop body. )

    class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
    
            int sz = nums.size()+1;
            vector<int> ret;
    #define CHEAT // on space
    #ifdef CHEAT
            bool presented[sz] = {};
            /* using either of the following 2 array forms is still accepted 
            char presented[sz] = {};
            vector<int> presented(sz);
            */
            for(int x : nums) {
                if(presented[x]) ret.push_back(x);
                else presented[x] = true;
            }
    #elif 0 //using bitwise inverse
            for(int i=1;i<sz;++i) {
                int n = max(arr[i],~arr[i]);
                if(arr[n] < 0) ret.push_back(n);
                else arr[n] = ~arr[n];
            }
    #else //swap based
            int* arr = nums.data()-1;
            for(int i=1;i<sz;) {
                if(!arr[i] || arr[i] == i) {
                    ++i;
                } else if(arr[i] == arr[arr[i]]) {
                    ret.push_back(arr[i]);
                    arr[i] = arr[arr[i]] = 0; // remove the number by setting zero
                    ++i;
                } else {
                    swap(arr[i],arr[arr[i]]);
                }
            }
    #endif
            return ret;
        }
    };
    

Log in to reply
 

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