如何在 Python 中有效检测并突出显示 2D 网格中的重叠区域？

Question

我有一个部分排序的大型整数数组，这意味着数组的某些部分是有序的，但其他部分则不是。我需要有效地找到该数组中最小的缺失正整数（大于 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. 如何利用数组的部分排序特性来提高性能？

Answer 1

我不确定这个解决方案比提议的解决方案更好，我只是将其交给那些能够阐明它的人考虑......

int getMinimumMissing( int arr[] ) {
    int max = 0;
    List<Integer> weHave = new ArrayList<>();
    List<Integer> WeAreMissing = new ArrayList<>();
    for( int i = 0; i < arr.length; i ++ ) {
        if( arr[ i ] > max ) {
            for( int j = max + 1; j < arr[ i ]; j ++ ) {
                WeAreMissing.add( j );
            }
            weHave.add( arr[ i ] );
            max = arr[ i ];
        }
        else {
            WeAreMissing.remove( Integer.valueOf( arr[ i ] ) );
        }
    }
    if( WeAreMissing.size() == 0 )
        return weHave.get( weHave.size() - 1 ) + 1;
    return WeAreMissing.get( 0 );
}