首页 > 代码库 > leetcode-First Missing Positive
leetcode-First Missing Positive
https://leetcode.com/problems/first-missing-positive/#/description
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.
题解：这道题目比较简单，需要注意的是几个陷阱：数组为空，数组里数据重复。
比较有技巧的地方是O(1)space，因为考虑到数据重复，此处只能排序， 这就要求重用nums数组空间。
引用网上一位网友的题解：
Put each number in its right place.For example:When we find 5, then swap it with A[4].At last, the first place where its number is not right, return the place + 1.
程序：
1 class Solution { 2 public: 3 int firstMissingPositive(vector<int>& nums) { 4 for (int i = 0; i < nums.size(); i++) 5 { 6 while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i] -1]) 7 { 8 swap(nums[i], nums[nums[i] -1]); 9 }10 }11 for (int i = 0; i < nums.size(); i++)12 {13 if (nums[i] != i + 1)14 {15 return i + 1;16 }17 }18 return nums.size() + 1;19 }20 };
leetcode-First Missing Positive
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。