19.2.4 [LeetCode 41] First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

题意

找到数组中最小的没出现的正整数

题解

一开始用空间换时间还是慢

还发现限制了空间，肯定没法用这种方法

 1 class Solution {
 2 public:
 3     int firstMissingPositive(vector<int>& nums) {
 4         vector<bool>visited(nums.size()+2,false);
 5         int size = nums.size();
 6         for (int i = 0; i < size; i++) {
 7             if (nums[i] <= size&&nums[i]>=1)
 8                 visited[nums[i]] = true;
 9         }
10         for (int i = 1; i < size + 2; i++)
11             if (!visited[i])return i;
12         return -1;
13     }
14 };

View Code

稍微改了一下，用原数组来存储，思路是按顺序在数组从下标0开始排1，2，3...不过没有变快就是了

 1 class Solution {
 2 public:
 3     int firstMissingPositive(vector<int>& nums) {
 4         int size = nums.size(), p = 0;
 5         while (p < size) {
 6             if (nums[p] == p + 1) {
 7                 p++;
 8                 continue;
 9             }
10             int tmp = nums[p];
11             if (tmp <= size && tmp > p && tmp != nums[tmp-1]) {
12                 nums[p] = nums[tmp - 1];
13                 nums[tmp - 1] = tmp;
14             }
15             else {
16                 nums[p] = nums[size - 1];
17                 size--;
18             }
19         }
20         return p + 1;
21     }
22 };

View Code

惊了，改用了swap函数就变快了，不知swap咋写的

 1 class Solution {
 2 public:
 3     int firstMissingPositive(vector<int>& nums) {
 4         int size = nums.size(), p = 0;
 5         while (p < size) {
 6             if (nums[p] == p + 1) {
 7                 p++;
 8                 continue;
 9             }
10             int tmp = nums[p];
11             if (tmp <= size && tmp > p && tmp != nums[tmp - 1])
12                 swap(nums[p], nums[nums[p] - 1]);
13             else {
14                 nums[p] = nums[size - 1];
15                 size--;
16             }
17         }
18         return p + 1;
19     }
20 };

View Code