龙

哇咔咔

0%

LeetCode 41 First Missing Positive

发表于 分类于 Disqus：
Leetcode第41题，找缺失的连续整数，级别：Hard。

Description:

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

题目理解：问题倒是十分的简单，所以这道题hard的原因在于固定的额外空间，也就是要原址操作。

如果不要求原址操作，那就是easy，但是原址操作的确也是不太好想，最后一瞬间想到了散列表，就想到这题的解法了， 也就是将一个数放到它应该在的位置上，比如数字5，那么它就该在数组的4位置上，那么通过直接索引加上交换， 就能实现题目要求。

PS:之前写的没有考虑固定空间，辣鸡。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int firstMissingPositive(int[] nums) {
        int right = nums.length - 1, i = 0;
        while ( i <= right ) {
            int idx = nums[i] - 1;
            if ( idx == i ) {
                i++;
            } else if ( idx > right || idx < 0 || nums[idx] == nums[i] ) {
                nums[i] = nums[right];
                right--;
            } else {
                nums[i] = nums[idx];
                nums[idx] = idx + 1;
            }
        }
        return right + 2;
    }
}

额外空间只使用了三个int，循环每次都操作一个数，或是放到最后，或者正确位置，并且同一个位置最多会被交换一次，所以复杂度是O(n)的。

复杂度：O(n)。
运行时间：12ms。
击败：56.77%

image