leetcode-find-missing-positive

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/first-missing-positive/

　　无序数组找到第一个缺失的正整数

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

　　注意时间复杂度是O(n)，空间复杂度是O(1)

题目分析

　　思路参考了disscuss区中思路。 既然空间复杂度要求O(1)，可以不断交换元素，从前向后遍历数组，数组位置i正确存放的值应该是i+1(由于是要求返回缺失的正整数)，如果不满足此条件，那么将该位置的元素值放入应该放入的数组位置，这时原来的位置又换来了一个新元素，不断检查循环，直到元素值不符合数组存放的正整数范围或者元素位置和元素值符合。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    
    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
    
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 1;
        }
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && i + 1 != nums[i] && nums[i] != nums[nums[i] - 1]) { // 这里还要注意条件 nums[i] != nums[nums[i] - 1] 否则会死循环！
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < len; i++) {
            if (i + 1 != nums[i]) {
                return i + 1;
            }
        }
        return len + 1;
    }
}