Leetcodes Solution 41 First Missing Positive

05-10

匯總

雪之下雪乃：leetcode解題總匯?

zhuanlan.zhihu.com

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,

and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

思路1

把每個正數從放相應索引的位置。

如把5放在nums[4]

然後再遍歷，第一個不對應的數就是我們要找的數

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