An O(n)-O(1) algorithm not using loop detection


  • 0
    P

    My friend wenx gives me a smart solution with O(n)-O(1) complexity. The idea is, first, we count the number of ones and zeros in the nums' lowest bit. If the ones beyond the normal number, we know that the lowest bit of the duplicate number is 1, otherwise is 0. Then in the next round, we will test the second lowest bit. In this round we will only test the numbers with the same lowest bit with the duplicate number( we have known it in the first round). And so on.

    int findDuplicate(vector<int>& nums) {
            int ret = 0;
            int lowMask = 0;
            for(int i=0;i<32;i++){
                int mask = 1<<i;
                int oneCnt = 0;
                int zeroCnt = 0;
                for(int j=0;j<nums.size();j++)if(i==0||ret==(nums[j]&lowMask)){
                    if((mask&nums[j])!=0)oneCnt++;
                    else zeroCnt++;
                }
                int allOne = 0;
                for(int j=1;j<nums.size();j++)if(i==0||ret==(j&lowMask))if((mask&j)!=0)allOne++;
                if(oneCnt>allOne)ret|=mask;
                lowMask = (lowMask<<1)|1;
            }
            return ret;
        }

  • 0

    In what way is it "new"? To me it looks like the same algorithm posted by some others before, for example here.


  • 0
    P

    tks, I didn't see that solution.


  • 1
    M

    And this Algorithm is not O(n)!!!!! This is O(nlog(n))
    Please note that 32 is log(n); and for bigger n you would need to check more bits


Log in to reply
 

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