41. First Missing Positive

题目描述和难度

  • 题目描述：

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

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

思路分析

求解关键：理解“桶排序”，元素放在它应该放的位置上，其它位置宁可空着。可以找其它相关的桶排序的问题来做。

参考解答

参考解答1

Java 写法：

import java.util.Arrays;

public class Solution {

    // 关键字：桶排序，什么数字就要放在对应的索引上，其它空着就空着
    // 最好的例子：[3,4,-1,1]
    // 整理好应该是这样：[1,-1,3,4]，
    // 这里 1，3，4 都在正确的位置上，
    // -1 不在正确的位置上，索引是 1 ，所以返回 2

    // [4,3,2,1] 要变成 [1,2,3,4]，剑指 Offer 上有类似的问题。

    // 这里负数和大于数组长度的数都是"捣乱项"。

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            // 前两个是在判断是否成为索引
            // 后一个是在判断，例如 3 在不在索引 2 上
            // 即 nums[i] ?= nums[nums[i]-1] 这里要特别小心
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 第 3 个条件不成立的索引的部分是 i 和 nums[i]-1
                swap(nums, nums[i] - 1, i);
            }
        }

        // 调试代码
        // System.out.println(Arrays.toString(nums));

        for (int i = 0; i < len; i++) {
            // [1,-2,3,4]
            // 除了 -2 其它都满足： i+1 = num[i]
            if (nums[i] - 1 != i) {
                return i + 1;
            }
        }

        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // int[] nums = {3, 4, -1, 5};
        int[] nums = {4, 3, 2, 1};
        int firstMissingPositive = solution.firstMissingPositive(nums);
        System.out.println(firstMissingPositive);
    }
}

Python 写法：

class Solution:

    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # 题目中给出的例子，就是最好的例子
        # [3,4,-1,1]
        # [-1,4,3,1]
        # [-1,1,3,4]
        # 3 应该放在索引为 2 的地方
        # 4 应该放在索引为 3 的地方

        for i in range(len(nums)):

            # nums[i] > 0 and nums[i] <= len(nums) 的意思是：只要是符合索引的数字
            # 这里的索引应该认为从 1 开始
            # 就要把它放到正确的地方上去，这一步叫 hash
            # nums[i] == nums[nums[i]-1]，叫放到了正确的地方
            # 例如，3 应该放在索引为 2 的地方，如果不理解，这句话多读几遍
            # 例如，3 应该放在索引为 2 的地方，如果不理解，这句话多读几遍
            # 例如，3 应该放在索引为 2 的地方，如果不理解，这句话多读几遍

            # 所以，先判断这个数字是不是索引
            # 然后判断这个数字是不是放在了正确的地方

            while 1 <= nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
                # 交换
                self.__swap(nums, i, nums[i] - 1)

        # 再遍历一次，没有放对的就是你要找的

        for i in range(len(nums)):
            # value： [1,2,3,4]
            # index： [0,1,2,3]
            if i + 1 != nums[i]:
                return i + 1

        return len(nums) + 1

    def __swap(self, nums, index1, index2):
        nums[index1], nums[index2] = nums[index2], nums[index1]

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0041-first-missing-positive ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。