標(biāo)簽： C++ 算法 LeetCode 數(shù)組
每日算法——leetcode系列
問題 First Missing Positive
Difficulty: Hard
Given an unsorted integer array, find the first missing positive integer.
For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.Your algorithm should run in O(n) time and uses constant space.
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
}
};
翻譯
第一個(gè)缺失的正整數(shù)
難度系數(shù)：困難
給定一個(gè)無序數(shù)組霎终，找出第一個(gè)缺失的正整數(shù)。
例如：
給定[1,2,0] 返回 3,
[3,4,-1,1] 返回 2鲜棠。
算法的時(shí)間復(fù)雜度為O(n), 空間復(fù)雜度為常數(shù)呈宇。
思路
此題一看想排序，如果有序后疯淫，找第一個(gè)缺失的正整數(shù)活翩，那就從1開始查畜埋，如果數(shù)組中查到有1，那就查2烟瞧，如此查到最后看待查的數(shù)就是要的結(jié)果诗鸭，要查的數(shù)可以用索引來表示。
排序算法時(shí)間復(fù)雜度為O(n)的是桶排序参滴，這里關(guān)鍵是要找到桶的個(gè)數(shù)强岸，由于只查正整數(shù)，假定數(shù)組的長序?yàn)閚砾赔，那n-1個(gè)桶放正整數(shù)就夠了蝌箍，遍歷數(shù)組，小于1和大于n-1的數(shù)都不用管暴心，這樣就可以把數(shù)組中1到n-1的數(shù)剔出放在相應(yīng)位置的桶中妓盲，再查缺失元素，但這種方案空間復(fù)雜度為O(n)专普，不為常數(shù)悯衬。
下面分析排序：
假定： 桶k裝的數(shù)為m
- k == m 不變
- k != m 則數(shù)m應(yīng)該裝到第m個(gè)桶，則把桶m的數(shù)和桶k的數(shù)交換檀夹，直接交換過來的數(shù)為m就不用交換
這里可能會(huì)給人感覺時(shí)間復(fù)雜度不為O(n)了甚亭，由于每一次交換后都會(huì)把一個(gè)數(shù)放到正確的桶上，所以平均下來最后還是O（n）
代碼
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
// sort
int n = static_cast<int>(nums.size());
int num;
for(int i = 0; i < n; ++i) {
num = nums[i];
while (num > 0 && num < n && nums[num-1] != num) {
swap(nums[i], nums[num-1]);
num = nums[i];
}
}
// find
int wantToFind = 1;
for (auto &item : nums){
if (item == wantToFind){
++wantToFind;
}
}
return wantToFind;
}
};
嘮叨
教初中娃兒編程真是一個(gè)難事击胜，能力不足亏狰，想要培養(yǎng)一個(gè)孩子的編程興趣還完全做不到
