C++ O(n) with O(1) space complexity which beats 94.98%


  • 0
    L
    int findDuplicate(vector<int>& nums) {
            int len = nums.size(), index = 0, tmpNum;
            while(index < len)
            {
                if(nums[index] != index + 1)
                {
                    tmpNum = nums[index];
                    if(nums[tmpNum - 1] != tmpNum)
                    {
                        nums[index] = nums[tmpNum - 1];
                        nums[tmpNum - 1] = tmpNum;
                    }
                    else
                    {
                        return tmpNum;
                    }
                }
                else
                {
                    index ++;
                }
            }
            return -1;
        }
    

Log in to reply
 

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