Лучший алгоритм поиска, чтобы найти не присутствует

Question

Лучший алгоритм поиска для поиска не присутствующего числа в диапазоне чисел

У меня есть следующий диапазон чисел в массиве: [3, -2, -1, 5, 6,7, -9 0, 1,2,3,5,7] В начале я изменяю массив на Set и использую фильтр, чтобы получить только положительные числа, и использую stream (). Sorted () для сортировки как c.

В списке результатов мне нужно найти первое число, отсутствующее. Я реализовал линейный алгоритм поиска, в котором я проверяю, меньше ли позиция следующего значения минус значение текущей позиции меньше 2, если истина, нет ли числа между текущим значением позиции и значением следующей позиции, если ложь, я возвращаю это число нет.

Проблема в том, что не знаю, есть ли способ повысить производительность, но я знаю, какой линейный алгоритм является наиболее затратным для поиска.

Мой код

public static int nopresentnumber(int[] array) {
        if (array == null)
            return 1;
        if (array.length == 0)
            return 1;
        final List<Integer> list = 
                                Arrays.stream(array)
                                    .boxed()
                                    .filter(n -> n > 0)
                                    .sorted()
                                    .collect(Collectors.toSet())
                                    .stream()
                                    .collect(Collectors.toList());
        final int listSize = list.size();
        if (listSize == 0)
            return 1;
        final int min = list.get(0);
        if (min > 1)
            return 1;
        for (int i = 0; i < listSize; i++) {
            if (i < listSize - 1) {
                final int x = list.get(i + 1) - list.get(i);
                if (x > 1)
                    return list.get(i) + 1;
            }
        }
        return list.get(listSize - 1) + 1;
    }

Использовать на небольших диапазонах неплохо. На примере массива [3, -2, -1, 5, 6,7, -9, 0, 1,2,3,5,7], ответ равен 4. Но если диапазон очень большой и имеет столько порядкового номера, алгоритм так плох. На примере оранжевого [-100000 ... до -100000] алгоритм будет проверен 99999 раз.

Answer 1

 [3, -2, -1, 5, 6,7, -9, 0, 1, 2, 3, 5, 7]

Ответ на этот вопрос, похоже, -8, учитывая тот факт, что мы учитываем отрицательные числа и ищем следующее последовательное пропущенное число.

Мое решение ниже учитывает отрицательные числа, но если вам нужны только положительные значения, нетрудно добавить простые if проверки.

---

Фрагмент:

import java.util.*;
class MyClass {
    public static void main(String args[]) {
      System.out.println(solve(new int[]{3, -2, -1, 5, 6,7, -9, 0, 1,2,3,5,7}));
    }

    private static int solve(int[] arr){
        Set<Integer> set = new HashSet<>();
        int minimum = arr[0];
        for(int x : arr){
            set.add(x);
            if(minimum > x) minimum = x;
        }

        int find_missing_num = minimum - 1; // just to compare with a base value.

        for(int x : arr){
            if(!set.contains(x-1)){
                if(find_missing_num == minimum - 1 && (x-1) != minimum - 1 || find_missing_num > x - 1) find_missing_num = x - 1;
            }   

            if(!set.contains(x+1)){
                if(find_missing_num == minimum - 1 && (x+1) != minimum - 1 || find_missing_num > x + 1) find_missing_num = x + 1;
            }
        }

        return find_missing_num;
    }
}

Демонстрация: https://ideone.com/KPoiXR

---

Алгоритм:

• Сначала создайте Set и добавьте все значения массива в набор.
• Во-вторых, снова выполните итерацию по массиву и проверьте наличие array_element - 1 и array_element + 1.
• Если мы не найдем их, мы соответствующим образом обновим find_missing_num в нашем коде.
• Сложность времени: O (n), Сложность пространства: O (n), где n - размер массива.

---

Чтобы найти первый отсутствующий положительный результат (а также игнорируя все отрицательные числа в массиве):

import java.util.*;
class MyClass {
    public static void main(String args[]) {
      //System.out.println(solve(new int[]{3, -2, -1, 5, 6,7, -9, 0, 1,2,3,5,7}));
      System.out.println(solve(new int[]{-1,0,2,3}));
    }

    private static int solve(int[] arr){
        Set<Integer> set = new HashSet<>();
        int minimum = -1;
        for(int x : arr){
            if(x > -1){
                set.add(x);
                if(minimum > x) minimum = x;
            }
        }

        if(!set.contains(1)) return 1;

        int find_missing_num = - 1; // just to compare with a base value.

        for(int x : arr){
            if(x > -1){
              if(x-1 > 0 && !set.contains(x-1)){
                    if(find_missing_num == -1 || find_missing_num > x - 1) find_missing_num = x - 1;
              }   

              if(!set.contains(x+1)){
                  if(find_missing_num == -1 || find_missing_num > x + 1) find_missing_num = x + 1;
              } 
            }
        }

        return find_missing_num;
    }
}

* 1 050 * Демо: https://ideone.com/0gwugF

Answer 2

Вы можете использовать двоичный поиск O (log n) для поиска в вашем массиве.

Первый порядок вашего массива:

Arrays.sort(array);

Применить двоичный поиск:

int index = Arrays.binarySearch(array, valueToSearch)

binarySearch вернет значение, большее или равное нулю, если элемент найден. Иначе, это производит отрицательное значение, представляющее место, в которое элемент должен быть вставлен. Произведенное значение:

-(insertion point) - 1