題目描述

給定一個無重復元素的整數數組 nums，請你找出其中沒有出現的最小的正整數。

進階：

• 時間復雜度：O(n)
• 空間復雜度：O(1)

數據范圍：

• 數組元素 nums[i] 的值在 $?2^{31}\le nums[i]\le 2^{31}?1$ 之間。
• 數組長度 len(nums) 滿足 $0\le len(nums)\le 5\times 10^5$。

示例

示例 1

輸入：

[1, 0, 2]

輸出：

3

示例 2

輸入：

[-2, 3, 4, 1, 5]

輸出：

2

示例 3

輸入：

[4, 5, 6, 8, 9]

輸出：

1

題解

本題的關鍵點是尋找數組中最小的缺失正整數。由于數組中沒有重復的元素，我們可以利用數組下標和數值之間的關系來進行處理。具體步驟如下：

思路

1. 無效值處理：

   • 數組中值小于等于0或大于數組長度的數值不可能是我們要找的最小正整數，可以將它們替換為一個不會影響結果的數字（例如 numsSize + 1）。

2. 就地交換：

   • 數組中的每個數字應該位于它應處的位置。例如，數字 1 應該位于索引 0，數字 2 應該位于索引 1，以此類推。
   • 我們通過交換將數字放到正確的位置上。

3. 查找缺失的最小正整數：

   • 遍歷數組，找到第一個沒有正確放置的數字，返回它的索引對應的正整數。
   • 如果所有的數字都正確放置了，說明數組中包含了所有從 1 到 numsSize 的正整數，那么最小缺失正整數為 numsSize + 1。

代碼實現

#include <stdio.h>
#include <stdlib.h>/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** @param nums int整型一維數組 * @param numsLen int nums數組長度* @return int整型*/
int minNumberDisappeared(int* nums, int numsLen) {// 1. 將所有不合法的數值替換為 numsLen + 1for (int i = 0; i < numsLen; i++) {if (nums[i] <= 0 || nums[i] > numsLen) {nums[i] = numsLen + 1;}}// 2. 將每個數值放到它應該在的位置上for (int i = 0; i < numsLen; i++) {int num = abs(nums[i]);  // 獲取當前值的絕對值if (num <= numsLen && nums[num - 1] > 0) {nums[num - 1] = -nums[num - 1]; // 標記 num 已經出現}}// 3. 查找第一個沒有標記的正整數for (int i = 0; i < numsLen; i++) {if (nums[i] > 0) {return i + 1; // 返回缺失的第一個正整數}}// 4. 如果沒有缺失，返回 numsSize + 1return numsLen + 1;
}

代碼解釋

1. 無效值處理：

   if (nums[i] <= 0 || nums[i] > numsLen) {nums[i] = numsLen + 1;
   }
   

   • 將數組中所有小于等于0或大于 numsLen 的數值替換為 numsLen + 1，因為這些數值不可能是我們要找的最小正整數。

2. 就地交換：

   int num = abs(nums[i]);
   if (num <= numsLen && nums[num - 1] > 0) {nums[num - 1] = -nums[num - 1]; // 標記為已出現
   }
   

   • 對于每個數字 num，我們將它放到應該在的位置（即 num-1 的位置）。如果 num 在數組范圍內并且當前位置的數字是正數，就將該位置標記為負數，表示該數值已出現。

3. 查找缺失的最小正整數：

   if (nums[i] > 0) {return i + 1; // 返回缺失的第一個正整數
   }
   

   • 如果遍歷完數組后，遇到第一個正數，說明該索引對應的正整數是缺失的最小正整數。

4. 返回結果：

   • 如果所有 1 到 numsLen 的整數都已經出現，則返回 numsLen + 1。

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。我們遍歷數組三次：一次處理無效值，一次進行就地交換，一次查找缺失的最小正整數。
• 空間復雜度：O(1)，除了輸入數組外，沒有使用額外的空間，所有操作都在原數組上進行。

總結

難得的一道簡單的題目。。