41. First Missing Positive
給定一個未排序的整數數組 nums。返回在 nums 中不存在的最小正整數。
你必須實現一個時間複雜度為 O(n) 並且使用 O(1) 輔助空間的算法。
範例 1：
輸入：nums = [1,2,0] 輸出：3 解釋：範圍 [1, 2] 內的數字都在數組中。
Python
from typing import List
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# First, segregate positive numbers and move non-positive numbers out of consideration
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# After rearranging, the first index i such that nums[i] != i + 1
# will be the missing positive number
for i in range(n):
if nums[i] != i + 1:
return i + 1
# If all numbers from 1 to n are in their correct positions,
# then the missing number is n + 1
return n + 1
30.19MB, 368ms
C++
#include <vector>
using namespace std;
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// Segregate positive numbers and place them in their correct positions
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
// Identify the first missing positive number
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// If all numbers from 1 to n are in their correct positions,
// then the missing number is n + 1
return n + 1;
}
};
53.37MB, 62ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
const n = nums.length;
// Segregate positive numbers and place them in their correct positions
for (let i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
[nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
}
}
// Identify the first missing positive number
for (let i = 0; i < n; ++i) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
// If all numbers from 1 to n are in their correct positions,
// then the missing number is n + 1
return n + 1;
};
57.34MB, 61ms
