leetcode 41. 缺失的第一个正数
2020-11-02 本文已影响0人
Source_Chang
- 排序 + 遍历
C++：
class Solution {
public:
int partition(vector<int>& nums, int start, int end) {
int i = start;
int j = end;
while ( i != j ) {
while ( i < j && nums[j] >= nums[start] ) {
--j;
}
while ( i < j && nums[i] <= nums[start] ) {
++i;
}
if ( i < j ) {
std::swap(nums[i], nums[j]);
}
}
std::swap(nums[i], nums[start]);
return i;
}
void quickSort(vector<int>& nums, int start, int end) {
if ( end <= start ) {
return;
}
int index = partition(nums, start, end);
quickSort(nums, start, index - 1);
quickSort(nums, index + 1, end);
}
int firstMissingPositive(vector<int>& nums) {
if ( nums.size() == 0 ) {
return 1;
}
if ( nums.size() > 1 ) {
quickSort(nums, 0, nums.size() - 1);
}
if ( nums[0] > 1 ) {
return 1;
}
for ( int i = 1; i < nums.size(); ++i ) {
if ( nums[i] - nums[i - 1] > 1 ) {
if ( nums[i - 1] < 0 ) {
if ( nums[i] > 1 ) {
return 1;
}
} else {
// nums[i - 1] >= 0
if ( nums[i] != 1 ) {
return nums[i - 1] + 1;
}
}
}
}
if ( nums[nums.size() - 1] <= 0 ) {
return 1;
}
return nums[nums.size() - 1] + 1;
}
};
- 原地哈希法
C++：
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int length = nums.size();
for ( int i = 0; i < length; ++i ) {
while ( nums[i] > 0 && nums[i] < length && nums[nums[i] - 1] != nums[i] ) {
std::swap(nums[i], nums[nums[i] - 1]);
}
}
for ( int i = 0; i < length; ++i ) {
if ( nums[i] != i + 1 ) {
return i + 1;
}
}
return length + 1;
}
};
