Another perspective: swap and compare


  • 0
    S

    I want to use the number-index relationship for this problem, yet there might be a number that if I use it as an index it will be out of range. So I first push back a new item to avoid this problem. For example, the array [3,2,0] will become [3,2,0,3].

    Then I swap numbers in the array so that the array becomes sorted->[0,2,3,3]

    Finally if nums[i+1] <= nums[i], i is the missing number.

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

Log in to reply
 

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