首页 > 代码库 > Leetcode:First Missing Positive 第一个缺失的正数 桶排序
Leetcode:First Missing Positive 第一个缺失的正数 桶排序
First Missing Positive：
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.
题解分析：
如果是T(n)的时间 T(n)的空间，则非常简单，首先遍历完数组，建立hash表，第二轮遍历直接找出第一个缺失的正数
class Solution {public: int firstMissingPositive(int A[], int n) { assert(A != NULL && n >= 0); unordered_set<int> numSet; for (int i = 0; i < n; ++i) { numSet.insert(A[i]); } for (int i = 1; ; ++i) { auto iter = numSet.find(i); if (iter == numSet.end()) { return i; } } }};
空间复杂度O(1)的解法：
桶排序的思想，最基本的思想就是 每个元素都归位到固定编号的桶内
这里正常情况下，应该是 1放在index = 0位置上，2放在index = 1的位置上，类似的，我们可以理解为 A[i]应该归位到编号为A[i]-1的桶内
当A[i] = i + 1时，元素已经位于正确的桶内了，直接跳过
当A[i] != i + 1时，我们不断的 交换 A[i] 与 A[A[i] - 1] 这两个值，直到发生以下情况：
a. A[i] = i + 1，循环结束
b. 因为与 A[A[i] - 1]做交换，所以 A[i] - 1作为下标必须符合范围，即 1 <= A[i] <= n，否则直接break
class Solution {public: int firstMissingPositive(int A[], int n) { bucketSort(A, n); for (int i = 0; i < n; ++i) { if (A[i] != i + 1) { return i + 1; } } return n + 1; } void bucketSort(int A[], int n) { assert(A != NULL && n >= 0); for (int i = 0; i < n; ++i) { while (A[i] != i + 1) { if (A[i] <= 0 || A[i] > n || A[i] == A[A[i] - 1]) { break; } std::swap(A[i], A[A[i] - 1]); } } }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。