一【題目類別】

• 哈希表

二【題目難度】

• 困難

三【題目編號】

• 41.缺失的第一個正數

四【題目描述】

• 給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
• 請你實現時間復雜度為 O(n) 并且只使用常數級別額外空間的解決方案。

五【題目示例】

• 示例 1：

  • 輸入：nums = [1,2,0]
  • 輸出：3

• 示例 2：

  • 輸入：nums = [3,4,-1,1]
  • 輸出：2

• 示例 3：

  • 輸入：nums = [7,8,9,11,12]
  • 輸出：1

六【題目提示】

• $1<=nums.length<=5?10^5$
• $?2^{31}<=nums[i]<=2^{31}?1$

七【解題思路】

• 對數組中的元素進行“原地哈希”，第i個元素映射到i-1的位置
• 這樣，對于1-N中的元素，如果沒有空缺，那么缺失的第一個正數一定是N+1；如果有空缺，那么缺失的第一個整數一定在1-N中
• 然后我們遍歷數組，對于映射不匹配的元素直接返回即可

八【時間頻度】

• 時間復雜度：$O(n)$，$n$為傳入的數組的長度
• 空間復雜度：$O(1)$

九【代碼實現】

1. Java語言版

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(nums[i] != i + 1){return i + 1;}}return n + 1;}public void swap(int[] nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

2. C語言版

void swap(int* nums, int index1, int index2)
{int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;
}int firstMissingPositive(int* nums, int numsSize)
{int n = numsSize;for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(i + 1 != nums[i]){return i + 1;}}return n + 1;
}

3. Python語言版

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(0, n):while 1 <= nums[i] and nums[i] <= n and nums[nums[i] - 1] != nums[i]:self.swap(nums, nums[i] - 1, i)for i in range(0, n):if nums[i] != i + 1:return i + 1return n + 1def swap(self, nums, index1, index2):temp = nums[index1]nums[index1] = nums[index2]nums[index2] = temp

4. C++語言版

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(nums[i] != i + 1){return i + 1;}}return n + 1;}void swap(vector<int>& nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
};

十【提交結果】

1. Java語言版
   

2. C語言版
   

3. Python語言版
   

4. C++語言版