給你一個未排序的整數數組，請你找出其中沒有出現的最小的正整數。 示例1: 輸入: [1,2,0] 輸出: 3 示例2: 輸入: [3,4,-1,1] 輸出: 2 示例3: 輸入: [7,8,9,11,12] 輸出: 1 提示： 你的算法的時間複雜度應為O(n)，并且隻能使用常數級别的額外空間。

// // Created by tannzh on 2020/7/6. // /* * 給你一個未排序的整數數組，請你找出其中沒有出現的最小的正整數。 示例1: 輸入: [1,2,0] 輸出: 3 示例2: 輸入: [3,4,-1,1] 輸出: 2 示例3: 輸入: [7,8,9,11,12] 輸出: 1 提示： 你的算法的時間複雜度應為O(n)，并且隻能使用常數級别的額外空間。 */ #include <iostream> #include <vector> using std::vector; class Solution { public: int firstMissingPositive(vector<int>& nums) { auto n = nums.size(); for (int i=0; i<n; i) while (nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1]) std::swap(nums[i], nums[nums[i]-1]); for (int i=0; i<n; i) if (nums[i] != i 1) return i 1; return n 1; } }; int main(int argc, char **argv) { std::vector<int> nums1 = {1,2,0}; std::vector<int> nums2 = {3,4,-1,1}; std::vector<int> nums3 = {7,8,9,11,12}; Solution s; std::cout << s.firstMissingPositive(nums1) << std::endl; std::cout << s.firstMissingPositive(nums2) << std::endl; std::cout << s.firstMissingPositive(nums3) << std::endl; return 0; }

這道題，能把題意看明白，就很不容易了。

1,2,0 -> 0,1,2,3 -> size == 3 ^ 3,4,-1,1 -> -1,1,2,3,4 -> size == 4 ^

按照上述排列方式，就能很清晰的看出，First Missing Positive 的含義。這個數有如下幾個條件：

• 最大為 n 1. (想象第一個例子，極端情況為 1,2,3, 那麼 result 即為 4, 恰為 n 1)
• 最小為 1.
• 1 ~ n 1 中間，第一個缺的數，即為返回結果。(容易理解，如果 1~n 都沒有缺的，那麼結果一定是 n 1 了)

所以問題來了，怎麼能在一次疊代中找出缺的那個？想象我們大腦是如何一下子看出來的？嗯，排列。

但排列完，就已經耗費了 O(N)，又要花 O(N) 去确認缺的那個數。其實，我們真的是排完序才知道空缺嗎？顯然不是。

另外，這道題要求不能用額外的空間，即使往排序上想，也隻能想着如何 swap 了。

一般的排序，的确是比較複雜的。但仔細觀察這道題，能夠發現這個"排序"卻比較特殊，首先它是從 1 開始的，且連續。

這讓我們想到了神馬？沒錯，像序号，就如數據庫表的自增主鍵一樣！那麼找到缺的，豈不是一眼就看出來了？

如何能讓這個無序的數組，看起來像序号一樣呢？而且手段隻有 swap. 有了，序号我們是知道的啊，這樣 swap 就有明确的目的了。

index: 1, 2, 3, 4 array: 3, 4,-1, 1 ^ ^ --- swap(3,-1) -1, 4, 3, 1 ^ ^ --- swap(4, 1) -1, 1, 3, 4 ^ ^ --- swap(1,-1) 1,-1, 3, 4 ^

經過幾步 swap, 我們驚人的發現最終對不齊的那個序号（2 : -1）就是我們要的結果！我們嘗試用代碼描述上述過程：

for (int i=0; i<n; i) while (A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1]) // 前兩個條件限定範圍，最後是如果序号位置的值與當前值一樣，交換無意義 swap(A[i], A[A[i]-1]); for (int i=0; i<n; i) if (A[i] != i 1) return i 1; // 最後的檢查，一旦發現與序号不符，立刻返回 return n 1; // 如果都相符，那麼返回 n 1

6行，提交，最高效率 AC.(4ms)

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!