Another O(n), O(1) solution inspired by linked list


  • 0
    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            for (int i = 0; i < nums.size(); ++i){
                if (nums[i] == i) continue;
                int temp = nums[i];
                while (temp != i && temp != nums.size() && temp != nums[temp]){
                    int t = nums[temp];
                    nums[temp] = temp;
                    temp = t;
                }
                if (temp == i) nums[i] = i;
            }
            for (int i = 0; i < nums.size(); ++i){
                if (nums[i] != i) return i;
            }
            return nums.size();
        }
    };
    
    • This solution runs with O(n) time complexity and O(1) space complexity
    • inspired by problem 287. Find the Duplicate Number
    • the only flaw is that it will change the original vector

Log in to reply
 

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