首页 > 学院 > 开发设计 > 正文

LeetCode 41. First Missing Positive

2019-11-11 05:19:43
字体:
来源:转载
供稿:网友

描述 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.

分析 本质上是桶排序 (bucket sort),每当 nums[i]!= i+1 的时候,将 nums[i] 与 nums[nums[i]-1] 交换,直到无法 交换为止,终止条件是 nums[i]== nums[nums[i]-1]。

代码

class Solution {public: int firstMissingPositive(vector<int>& nums) { bucket_sort(nums); const int n = nums.size(); for (size_t i = 0; i < n; ++i) { if (nums[i] != i + 1) return i + 1; } return n + 1; }PRivate: static void bucket_sort(vector<int>& nums) { const int n = nums.size(); for (size_t i = 0; i < n; ++i) { while (nums[i] != i + 1) { if (nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1]) break; swap(nums[i], nums[nums[i] - 1]); } } }};
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表