LeetCode 41. First Missing Positive

这个题目虽然是Hard,但是只要想到解法之后,就很简单了。

题目要求:找到最小的、没有出现在数组中的整数,数组未排序。

初看起来,这个至少得排个序才能搞定。但是题目说了,时间复杂度O(n),空间复杂度O(1)。

如果能把数字n填写到第n-1个,那不就能在O(n)时间内看出来缺失数字了吗?把数字n填写到第n-1个,完全就是遍历一遍所有的数字就可以了啊。

思路就这样出来了:

  1. 遍历所有数字,将数字n放到第n-1个位
  2. 遍历数组,第一个不满足nums[i]!=i+1的i+1即为缺失的数字

代码如下:

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length;) {
            if (nums[i] > 0 && nums[i] <= nums.length) {
                if (nums[nums[i] - 1] == nums[i]) {
                    // 两者相等就没有必要交换了,next
                    i++;
                    continue;
                }
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
                // 交换完成之后,我们并不能确保当前的nums[i]在该在的位置上了
                // 所以不能贸然处理下一个
                // 这是一个坑
            }
            if (nums[i] <= 0 || nums[i] > nums.length || nums[i] == i + 1) {
                // 要么这个数字不在0-n内,要么这个数字已经在该在的位置上了
                // 总而言之,next
                i++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                // 所有在范围内的数字都已经到对应位置了
                // 但这个位置没有对应的数字,所以这个数字是缺失了的
                return i + 1;
            }
        }
        // 从0-n都有,所以缺失了n+1
        return nums.length + 1;
    }
}

第一个for循环,虽然i并不一定在每次循环的时候递增,但是总的时间复杂度还是O(n):

对于所有的数字,要不交换到对应位置,要么不交换:即O(n)。

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.