Java如何找出缺失的第一个正数

在编程中，我们经常会遇到需要找出数组中缺失的第一个正数的问题。这个问题在算法面试中也非常常见。本文将介绍如何使用Java来解决这个问题。

问题描述

给定一个未排序的整数数组，找出其中缺失的第一个正数。例如，给定数组 [3, 4, -1, 1]，缺失的第一个正数是 2。

解决思路

要解决这个问题，我们可以使用一种称为“原地哈希”的技术。具体步骤如下：

1. 过滤非正数：首先，我们可以忽略数组中的非正数（即小于等于0的数），因为它们不会影响我们寻找缺失的正数。

2. 原地哈希：我们可以利用数组本身来记录哪些正数已经出现过。具体来说，我们可以将数组中的每个正数 nums[i] 放到数组的第 nums[i] - 1 个位置上。这样，如果数组中的某个位置 i 上的数不等于 i + 1，那么 i + 1 就是缺失的第一个正数。

3. 遍历数组：最后，我们只需要遍历数组，找到第一个不满足 nums[i] == i + 1 的位置，返回 i + 1 即可。如果数组中的所有位置都满足条件，那么缺失的第一个正数就是数组长度加1。

代码实现

以下是使用Java实现的代码：

public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 第一步：将非正数替换为 n + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        // 第二步：原地哈希
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 第三步：找出第一个缺失的正数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果数组中的所有位置都满足条件，返回 n + 1
        return n + 1;
    }

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组三次。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

总结

通过原地哈希的方法，我们可以在O(n)的时间复杂度和O(1)的空间复杂度内找出数组中缺失的第一个正数。这种方法不仅高效，而且代码实现也相对简单。希望本文能帮助你更好地理解和解决这个问题。