My 12 line c++ solution, but I don't known why it's O(n), anyone can explain to me? Thanks.


  • -1
    8
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int result = 1;
            for (int i = 0; i < nums.size(); ) {
                if (nums[i] != result) {
                    i++;
                } else {
                    // swap 
                    int temp = nums[result - 1];
                    nums[result - 1] = nums[i];
                    nums[i] = temp;
                    i = result++;
                } 
            }
            return result;
        }
    };

  • 0
    Z

    I think it is not O(n).
    For the case[10,9,8,7,6,5,4,3,2,1], the missing number is 9.
    The program will run several swap and loop, it does like a sort program..


  • 0
    F

    However, it is not O(n). It's apparently O(n2).


Log in to reply
 

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