Java中如何根据系统负载动态调整线程池大小？

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

Answer 2

（注意：我不是算法人）

由于这本质上是一个排序问题，所以如果在平均情况下你能做得比 O(n log n) 更好，我会感到惊讶。然而，你说数组是部分有序的，所以也许Timsort排序算法可能是合适的。

当然，如果最大整数值已知并且具有合理的低量级，以便仅分配索引数组并标记所见值的存在，可能会有更快的解决方案。

Answer 3

如果允许重新排列输入数组，则可以通过移动可能形成从 1 开始的连续序列的正元素（使用它们的值减 1 作为索引）来解决这个问题，而无需线性时间的额外空间。

public static int findSmallestMissingPositive(int[] arr) {
    for (int i = 0; i < arr.length;) {
        int cur = arr[i];
        if (cur > 0 && cur <= arr.length && arr[cur - 1] != cur) {
            arr[i] = arr[cur - 1];
            arr[cur - 1] = cur;
        } else ++i;
    }
    int missing = 1;
    while (missing <= arr.length && arr[missing - 1] == missing) ++missing;
    return missing;
}