LeetCode 第 41 题：缺失的第一个正数

题目地址	题解
LeetCode 第 41 题：缺失的第一个正数	桶排序（Python 代码、Java 代码）

提示：点击上面的题解链接，可以看到我制作的幻灯片轮播图。

这道题使用桶排序的思路，即 “一个萝卜一个坑”，就可以解决。可以就使用题目中的例子，在纸上写写画画，就能得出思路，只不过在编码上需要注意一些细节。

下面是“桶排序”过程。

LeetCode 第 41 题：缺失的第一个正数-1

LeetCode 第 41 题：缺失的第一个正数-2

LeetCode 第 41 题：缺失的第一个正数-3

LeetCode 第 41 题：缺失的第一个正数-4

LeetCode 第 41 题：缺失的第一个正数-5

LeetCode 第 41 题：缺失的第一个正数-6

LeetCode 第 41 题：缺失的第一个正数-7

LeetCode 第 41 题：缺失的第一个正数-8

LeetCode 第 41 题：缺失的第一个正数

如图所示：我们可以把数组进行一次“排序”，“排序”的规则是：如果这个数字 i 落在“区间范围里”，i 就应该放在索引为 i - 1 的位置上，下面具体解释。

1、数字 i 落在“区间范围里”；

例如：[3, 4, -1, 1]，一共 4 个数字，那么如果这个数组中出现 “1”、“2”、“3”、“4”，就是我们重点要关注的数字了；
又例如：[7, 8, 9, 11, 12] 一共 5 个数字，每一个都不是 “1”、“2”、“3”、“4”、“5” 中的一个，因此我们无须关注它们；

2、i 就应该放在索引为i - 1 的位置上；

这句话也可以这么说 “索引为 i 的位置上应该存放的数字是 i + 1”。

就看上面那张图，数字 $1$ 应该放在索引为 $0$ 的位置上，数字 $3$ 应该放在索引为 $2$ 的位置上，数字 $4$ 应该放在索引为 $3$ 的位置上。一个数字放在它应该放的位置上，我们就认为这个位置是“和谐”的，看起来“顺眼”的。

按照以上规则排好序以后，缺失的第 $1$ 个正数一下子就看出来了，那么“最不和谐”的数字的索引 $+ 1$ ，就为所求。那如果所有的数字都不“和谐”，数组的长度 $+ 1$ 就为所求。

Python 代码：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        size = len(nums)
        if size == 0:
            return 1
        
        for i in range(size):
            
            while nums[i] > 0 and nums[i] <= size:
                if nums[nums[i] - 1] == nums[i]:
                    # 如果已经在合适的位置上，就不用交换了
                    break
                # 这里我单独把交换数组两个位置的方法封装起来，是为了不让自己出错，这一行代码有点绕
                # 就要把它放到合适的位置上，i 应该放在索引为 i - 1 的位置上
                self.__swap(nums, i , nums[i] - 1)
        
        
        # 从头到尾看一遍
        for i in range(size):
            if nums[i] != i + 1:
                return i + 1
        return size + 1
               
            
    def __swap(self, nums, index1, index2):
        if index1 == index2:
            return
        nums[index1], nums[index2] = nums[index2], nums[index1]

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);
    }
}

复杂度分析：