[LeetCode] 41. First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

缺失的第一个正数。

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

注意这道题对时间空间复杂度是有要求的，因为时间要求是 O(n) 所以没法排序；也不允许使用额外空间，所以不能用 hashmap 或者 hashset。那么这题的思路就只能是类似桶排序/抽屉原理，需要在对应的坐标上找到对应的数字，即数字 i 应该出现在坐标为 i - 1 的位置上，这样也能排除负数和大于数组长度的正数。 按照这个思路，需要扫描两遍，第一遍是将所有大于 0 且小于数组长度的正整数放到他们应该去的位置上，因为只有这些数字可以跟下标形成对应关系。第二遍再次扫描 input 的时候就能找出第一个缺失的正数了。

复杂度

时间O(n) - 题目要求
空间O(1) - 题目要求

代码

Java实现

class Solution {
	public int firstMissingPositive(int[] nums) {
		// corner case
		if (nums == null || nums.length == 0) {
			return 1;
		}

		// normal case
		for (int i = 0; i < nums.length; i++) {
			// 如果swap的动作按照注释中的部分写
			// 一定要把nums[nums[i] - 1]先赋值给temp，否则如下的case是会越界的
			// [3, 4, -1, 1]
			while (nums[i] > 0 && nums[i] < nums.length && nums[nums[i] - 1] != nums[i]) {
				// int temp = nums[nums[i] - 1];
				// nums[nums[i] - 1] = nums[i];
				// nums[i] = temp;
				swap(nums, i, nums[i] - 1);
			}
		}

		// double check
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != i + 1) {
				return i + 1;
			}
		}
		return nums.length + 1;
	}

	private void swap(int[] nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
    // corner case
    if (nums === null || nums.length === 0) return 1;

    // normal case
    for (let i = 0; i < nums.length; i++) {
        while (nums[i] > 0 && nums[i] < nums.length && nums[nums[i] - 1] !== nums[i]) {
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }

    // double check
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;
};

相关题目

41. First Missing Positive
268. Missing Number
442. Find All Duplicates in an Array
448. Find All Numbers Disappeared in an Array
765. Couples Holding Hands