首页 > 代码库 > Leetcode:First Missing Positive 第一个缺失的正数 桶排序

Leetcode:First Missing Positive 第一个缺失的正数 桶排序

2024-07-10 07:06:15   221人阅读

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]);            }        }    }};

 


联系
我们