Как эффективно найти наименьшее недостающее положительное целое число в большом частично отсортированном массиве в Java? ⇐ JAVA

[Anonymous]

У меня есть большой массив целых чисел, который частично отсортирован. Это означает, что некоторые части массива находятся в порядке, а другие — нет. Мне нужно найти наименьшее недостающее положительное целое число (больше 0) в этом массиве без полной сортировки всего массива.
Например:
Ввод:
arr = [3, -1, 4, 1, 5, 0, 2]
Ожидаемый результат:
6 (как 1, 2, 3) , 4 и 5 присутствуют, но 6 — это наименьшее отсутствующее положительное целое число).
Я написал следующий код Java, используя HashSet для отслеживания наличия чисел, а затем прошёл цикл, чтобы найти наименьшее пропущенное положительное целое число:

Код: Выделить всё

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 seen = new HashSet();
for (int num : arr) {
if (num > 0) {
seen.add(num);
}
}

int smallestMissing = 1;
while (seen.contains(smallestMissing)) {
smallestMissing++;
}

return smallestMissing;
}

Этот код работает, но не оптимален для очень больших массивов. Я хочу оптимизировать его дальше, возможно, без использования дополнительного пространства (например, путем изменения самого входного массива).
Мои вопросы:

[*]Есть ли способ решить эту проблему за время O(n) без дополнительного пространства?

[*]Как Могу ли я использовать частично отсортированный массив для повышения производительности?



Подробнее здесь: https://stackoverflow.com/questions/792 ... rge-partia