如何使用Java Lambda表达式查找数组中缺失的最小正整数

问题回顾 #

给定一个包含N个整数的数组A，我们需要实现函数返回数组中未出现的最小正整数（大于0），示例如下：

• 输入A = [1, 3, 6, 4, 1, 2]，返回5；
• 输入A = [1, 2, 3]，返回4；
• 输入A = [-1, -3]，返回1。

你提供的非Lambda参考代码核心思路是：先分离非正整数和正整数，然后在正整数子数组中通过标记对应索引位置的数值（取反）来快速定位缺失的最小正整数。下面我将基于这个思路，用Java Lambda表达式实现更简洁的高效版本，同时也提供一个更直观的实现供参考。

高效Lambda实现（O(n)时间复杂度） #

这个版本完全沿用了参考代码的高效逻辑，只是用Stream和Lambda简化了代码结构：

import java.util.Arrays;
import java.util.stream.IntStream;

public class SmallestMissingPositive {
    public static int findSmallestMissingPositiveEfficient(int[] arr) {
        // 过滤出所有正整数，对应原代码的segregate步骤
        int[] positiveNumbers = Arrays.stream(arr)
                .filter(num -> num > 0)
                .toArray();

        int length = positiveNumbers.length;

        // 标记已出现的正整数：将对应索引位置的数值取反
        IntStream.range(0, length)
                .forEach(index -> {
                    int current = Math.abs(positiveNumbers[index]);
                    if (current - 1 < length && positiveNumbers[current - 1] > 0) {
                        positiveNumbers[current - 1] = -positiveNumbers[current - 1];
                    }
                });

        // 找到第一个未被标记（仍为正数）的索引，对应缺失的最小正整数
        return IntStream.range(0, length)
                .filter(index -> positiveNumbers[index] > 0)
                .map(index -> index + 1)
                .findFirst()
                // 如果所有索引都被标记，说明1~length都存在，返回length+1
                .orElse(length + 1);
    }

    public static void main(String[] args) {
        // 测试示例
        System.out.println(findSmallestMissingPositiveEfficient(new int[]{1, 3, 6, 4, 1, 2})); // 输出5
        System.out.println(findSmallestMissingPositiveEfficient(new int[]{1, 2, 3})); // 输出4
        System.out.println(findSmallestMissingPositiveEfficient(new int[]{-1, -3})); // 输出1
        System.out.println(findSmallestMissingPositiveEfficient(new int[]{0, 10, 2, -10, -20})); // 输出1
    }
}

代码解释 #

1. 过滤正整数：用Arrays.stream(arr).filter(num -> num > 0).toArray()快速提取数组中的所有正整数，替代了原代码的segregate方法，代码更简洁。
2. 标记已存在的数：通过IntStream.range(0, length).forEach(...)遍历正整数数组，逻辑和原代码的findMissingPositive完全一致——如果当前数current对应的索引current-1在数组范围内，就将该索引的数值取反，标记这个数已经出现过。
3. 查找缺失的数：用IntStream.range(0, length).filter(...)找到第一个未被标记（数值仍为正）的索引，加1就是缺失的最小正整数；如果所有索引都被标记，说明1到length的正整数都存在，返回length+1。

直观Lambda实现（O(n log n)时间复杂度） #

如果追求代码的直观性，也可以用排序+流查找的方式实现，虽然时间复杂度稍高，但代码非常简洁：

import java.util.Arrays;
import java.util.stream.IntStream;

public class SmallestMissingPositive {
    public static int findSmallestMissingPositiveIntuitive(int[] arr) {
        // 过滤正整数、去重、排序
        int[] sortedPositives = Arrays.stream(arr)
                .filter(num -> num > 0)
                .distinct()
                .sorted()
                .toArray();

        // 从1开始查找第一个不在排序数组中的正整数
        return IntStream.iterate(1, i -> i + 1)
                .filter(i -> !Arrays.stream(sortedPositives).anyMatch(num -> num == i))
                .findFirst()
                .getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(findSmallestMissingPositiveIntuitive(new int[]{1, 3, 6, 4, 1, 2})); // 输出5
    }
}

这个版本的逻辑很直接：先把数组中的正整数去重排序，然后从1开始依次检查每个数是否存在于排序后的数组中，第一个不存在的就是答案。

内容的提问来源于stack exchange，提问作者Yatendragola