Share four different solutions


  • 12
    S
    // sort + binary seach 
    // O(nlogn) time, O(1) space
    int missingNumber1(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int m = 0;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            m = (l + r ) / 2;
            if (nums[m] == m) l = m + 1;
            else r = m - 1;
        }
        
        return nums[l] == l ? l + 1 : l;
    }
    
    // arithmetic progression
    // O(n) time, O(1) space
    int missingNumber2(vector<int>& nums) {
        int sum1 = 0;
        for (int x : nums) sum1 += x;
        int minV = 0, maxV = nums.size();
        int sum2 =  (minV + maxV) * (nums.size() + 1) / 2;
        return sum2 - sum1;
    }
    
    // XOR 
    // O(n) time, O(1) space
    int missingNumber3(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i <= nums.size(); ++i)
            ans ^= (i == nums.size()) ? i : i ^ nums[i];
        return ans;
    }
    
    // map table
    // O(n) time, O(1) space
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            while (nums[i] != i && nums[i] < nums.size() && nums[i] != nums[nums[i]]) 
                swap(nums[i], nums[nums[i]]);
        }
        
        for (int i = 0; i < nums.size(); ++i)
            if (nums[i] != i) return i;
            
        return nums.size();
    }

  • 0
    X

    If you are using sort() method, how come it would be O(n) linear time?


  • 0
    S

    that's O(nlgn) time, i have written it on the comment


  • 0
    W

    In the fourth solution, why did you add condition "nums[i] != nums[nums[i]]"? I believe this condition always holds.


Log in to reply
 

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