Share my thoughts. 4ms soln.


  • 6

    At beginning, I was thinking:

    1. it requires O(n), means no sorting/binary searching. You should only go through the numbers then get the result.
    2. no extra memory, means you can not use bit vector to indicate if any number exists.

    So, the first idea came into my mind is bit manipulation. But, after tried and thought it again, bit manipulation doesn't help here. Because the numbers can be duplicated. Re-visited the problem, I found one critical point: it's asking the smallest missing positive number. It means I can reorder the numbers to let the nums[0]=1, nums[1]=2... etc. Actually, I spent more than 30 minutes on bit manipulation direction. Once I found the solution, it only took about 10 minutes to code.

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

  • 0
    C

    Thank you! That's great.


Log in to reply
 

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