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

[Anonymous]

У меня есть большой набор целых чисел, который частично отсортирован, что означает, что некоторые части массива в порядке, а другие - нет. Мне нужно найти наименьшее недостающее положительное целое число (больше 0) в этом массиве эффективно, не полностью сортируя весь массив. < /P>
Например: < /p>
Ввод:
arr = [3, -1, 4, 1, 5, 0, 2] < /p>
Ожидаемый выход:
6 (как 1, 2, 3 , 4 и 5 присутствуют, но 6 - наименьшее отсутствующее положительное целое число). < /P>
Я написал следующий код Java, используя хэшсет, чтобы отслеживать наличие чисел, а затем процитировал, чтобы найти наименьшее недостающее положительное целое число: < /p>
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;
}
}
< /code>
Этот код работает, но не оптимально для очень больших массивов. Я хочу оптимизировать его дальше, потенциально без использования дополнительного пространства (например, путем изменения самого массива ввода). < /P>
Мои вопросы: < /p>

• Есть ли способ решить эту проблему в сложности времени O (n) без дополнительного пространства? < /p>
  < /li>
  Как Могу ли я использовать частично отсортированный характер массива для повышения производительности?

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