如何高效查找大型部分排序数组中缺失的最小正整数及优化方案

问题背景 #

我拥有一个大型的部分排序整数数组，即数组部分元素有序、部分无序。需要在不完整排序整个数组的前提下，高效找出其中缺失的最小正整数（大于0）。

示例 #

• 输入：arr = [3, -1, 4, 1, 5, 0, 2]
• 预期输出：6（因1、2、3、4、5均存在，6是缺失的最小正整数）

现有实现 #

我已编写以下使用HashSet的Java代码来追踪数字存在性，进而查找缺失的最小正整数：

import java.util.HashSet;

public class SmallestMissingPositive {
    public static void main(String[] args) {
        int[] arr = {3, -1, 4, 1, 5, 0, 2};
        System.out.println(findSmallestMissingPositive(arr));
    }
    
    public static int findSmallestMissingPositive(int[] arr) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : arr) {
            if (num > 0) {
                seen.add(num);
            }
        }
    
        int smallestMissing = 1;
        while (seen.contains(smallestMissing)) {
            smallestMissing++;
        }
    
        return smallestMissing;
    }
}

该代码可正常运行，但对于超大数组并非最优。我希望进一步优化，例如不使用额外空间（如直接修改输入数组）。

我的问题 #

1. 是否存在O(n)时间复杂度且无需额外空间的解法？
2. 如何利用数组的部分排序特性提升性能？

问题解答 #

1. O(n)时间、O(1)空间的解法 #

存在，核心思路是原地哈希：利用数组本身的索引作为哈希表的键，把每个正整数放到它对应的索引位置（比如数值x应该放在索引x-1处），之后遍历数组就能快速找到缺失的最小正整数。

具体步骤：

• 遍历数组，对于每个元素num：
  • 如果num是正整数，且num <= arr.length，且arr[num-1] != num，就交换num和arr[num-1]的位置，直到当前位置的元素不满足交换条件为止。
• 再次遍历数组，找到第一个索引i，使得arr[i] != i+1，那么i+1就是缺失的最小正整数。
• 如果所有位置都满足arr[i] == i+1，说明缺失的是arr.length + 1。

Java实现代码：

public class SmallestMissingPositive {
    public static void main(String[] args) {
        int[] arr = {3, -1, 4, 1, 5, 0, 2};
        System.out.println(findSmallestMissingPositive(arr));
    }
    
    public static int findSmallestMissingPositive(int[] arr) {
        int n = arr.length;
        
        // 原地哈希：将正整数放到对应的索引位置
        for (int i = 0; i < n; i++) {
            // 只处理符合条件的正整数，避免死循环
            while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {
                swap(arr, i, arr[i] - 1);
            }
        }
        
        // 查找第一个不匹配的位置
        for (int i = 0; i < n; i++) {
            if (arr[i] != i + 1) {
                return i + 1;
            }
        }
        
        // 所有1~n都存在，返回n+1
        return n + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

这个算法的时间复杂度是O(n)，因为每个元素最多被交换一次；空间复杂度是O(1)，只使用了常数额外空间。

2. 利用部分排序特性提升性能 #

部分排序数组意味着存在一些连续有序的子区间，我们可以利用这个特性减少不必要的操作：

• 提前终止交换：在原地哈希的交换步骤中，如果当前元素所在的子区间是有序的，且元素已经处于正确位置，可以直接跳过该子区间，不用逐个处理。
• 二分查找辅助：对于有序的子区间，我们可以用二分查找快速判断某个正整数是否存在，减少遍历次数。比如，当我们检查smallestMissing是否存在时，先在有序子区间里用二分查找，找不到再去无序部分处理。
• 分段处理：将数组分成有序段和无序段，先遍历有序段收集存在的正整数范围，再针对这些范围快速定位缺失值。比如，如果有序段包含1~k，那我们只需要在无序段里找k+1是否存在，若不存在则直接返回k+1，否则继续往后找。

举个简单的优化示例：假设数组前半部分有序，我们可以先遍历有序段，记录连续存在的最小正整数序列，比如从1开始，找到最大的连续值m，然后只需要在无序段里检查m+1是否存在，若不存在则直接返回m+1，否则继续往后找。这样可以减少后续需要处理的元素数量。

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