leetcode经典题(leetcodeC题解系列-040)(1)

题目

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例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 的含义。这个数有如下几个条件:

所以问题来了,怎么能在一次迭代中找出缺的那个?想象我们大脑是如何一下子看出来的?嗯,排列。

但排列完,就已经耗费了 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)

,