leetcode经典题（leetcodeC题解系列-040）

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 示例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)