Leetcode 041 First Missing Positive（桶排序）

本文主要是介绍Leetcode 041 First Missing Positive（桶排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Leetcode 041 First Missing Positive

解题思路：桶排序的变种，每次把碰到把nums[i] 和 nums[nums[i]] 互换，保证 nums[i] = nums[nums[i]]。当然nums[i]小于零，或者是大于数组的可以忽略。最后遍历一遍数组，第一个不匹配的位置即为答案。

class Solution {public:int firstMissingPositive(vector<int>& nums) {nums.push_back(0);int n = nums.size();for (int i = 0; i < n; i++) {while (nums[i] >= 0 && nums[i] < n) {if (nums[i] == i || nums[i] == nums[nums[i]]) break;int tmp = nums[i];nums[i] = nums[tmp];nums[tmp] = tmp;}}int ans = 1;while (ans < n && nums[ans] == ans) ans++;return ans;}
};

这篇关于Leetcode 041 First Missing Positive（桶排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---