Найти первый пропущенный номер в наборе

Question

Мне нужно найти первое пропущенное число из HashSet, например:

Set<Integer> h = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 6, 8, 9, 10));

В этом примере, если мы выполняем итерацию в первый раз, мы получим int freeNumber = 5;

Очевидно, что я могу сортировать и повторять цикл while, пока не найду пропущенное число. Но, похоже, это не оптимизированный или элегантный способ выполнения этой операции.

int i = 1;
for (Integer number : allFileNumbers) {
    if(number != i) {
        missing = number;
        break;
    }
    i++;
}

Answer 1

Если у вас есть TreeSet или любой NavigableSet в целом, вы можете использовать вариант Двоичный поиск , чтобы найти первое пропущенное значение:

static Integer firstMissing(NavigableSet<Integer> set) {
    if(set.size() <= 1) return null;
    Integer first = set.first(), last = set.last();
    if(set.size() == last - first + 1) return null; // no gaps at all
    while(true) {
        int middle = (first+last)>>>1;
        NavigableSet<Integer> sub = set.headSet(middle, false);
        if(sub.size() < middle - first) {// gap before middle
            set = sub;
            last = sub.last();
        }
        else {
            set = set.tailSet(middle, true);
            first = set.first();
            if(first != middle) return middle;
        }
    }
}

будет называться как

NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 6, 7, 8, 9, 10));
System.out.println(firstMissing(set));

Во-первых, поскольку Set не содержит дубликатов, мы можем использовать минимальное и максимальное число, чтобы вычислить, какой размер должен иметь набор последовательных чисел. Если набор имеет такой размер, мы знаем, что пробелов нет, и можем вернуться немедленно. В противном случае мы вычисляем среднее число и разбиваем множество на две части. Для первой половины набора мы можем выполнить тот же тест, чтобы определить, есть ли в нем разрыв, и продолжить работу только с той половиной набора, чтобы найти первый разрыв. В противном случае мы берем вторую половину, уже зная, что должен быть разрыв. Поиск заканчивается, когда этот набор не содержит нашего среднего числа.

Если у вас есть произвольный Set, без гарантированного порядка, лучшего способа сделать это не существует, так как каждый подход работает хорошо для одного ввода, но хуже для другого.

• Вы можете просто скопировать набор в TreeSet, используя new TreeSet<>(set), и использовать метод, описанный выше

• Вы можете переключаться между диапазонами номеров, чтобы проверить наличие, затем отсутствие чисел

      static Integer firstMissing(Set<Integer> set) {
          if(set.size() <= 1) return null;
          Integer firstPresent = null, firstAbsent = null;
          for(int i = Integer.MIN_VALUE; firstPresent == null; i++)
              if(set.contains(i)) firstPresent = i;
          for(int i = firstPresent+1; firstAbsent == null; i++)
              if(!set.contains(i)) firstAbsent = i;
          return firstAbsent-firstPresent == set.size()? null: firstAbsent;
      }
  

  Условия цикла используют предварительное тестирование, которое гарантирует, что в наборе есть как минимум два числа.

  Очевидная проблема - большой диапазон номеров, мы должны исследовать. Если мы знаем, что все числа положительные, мы можем заменить Integer.MIN_VALUE на ноль.

• вы можете перебирать содержимое набора, чтобы записывать все встречающиеся значения в доступную для поиска структуру данных. Это похоже на метод копирования, описанный выше, но, например, если все числа положительны, вы можете использовать следующий тест:

      static Integer firstMissing(Set<Integer> set) {
          if(set.size() <= 1) return null;
          BitSet bs = new BitSet();
          set.forEach(bs::set);
          int firstPresent = bs.nextSetBit(0), firstAbsent = bs.nextClearBit(firstPresent);
          return firstAbsent-firstPresent == set.size()? null: firstAbsent;
      }
  

  Он работает намного лучше, чем TreeSet, если пропущено только несколько чисел или их нет вообще, но гораздо хуже, если значения действительно редки.

Answer 2

Просто идея ...

Set<Integer> h = new HashSet<>(Arrays.asList(1, 2, 3, 4, 6, 8, 9, 10));
Set<Integer> k = IntStream.rangeClosed(Collections.min(h),Collections.max(h)).boxed().collect(Collectors.toSet());
k.removeAll(h);
System.out.println(k.stream().findFirst().orElse(-1));

Answer 3

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

Ваш лучший вариант - перебирать целые числа и проверять их наличие в множестве. Это простой подход, и он будет работать в O(k*p), где k - это наименьшее значение, отсутствующее в наборе, а p - это стоимость вызова Set.contains(). Если ваш набор имеет O(1) доступ для чтения, то вы получите O(k) алгоритм сложности, который является линейным.

Пример:

public int findFirstNotInSet(Set<Integer> values) {
    for (int i = 1; i < Integer.MAX_VALUE; i++) {
        if (!values.contains(i)) {
            return i;
        }
    }

    // handle edge case for Integer.MAX_VALUE here
}

Если вы можете сделать больше предположений относительно значений в наборе (диапазон, количество пропущенных значений, ...), то, вероятно, вы можете ускорить этот алгоритм.

Answer 4

Вы можете найти с потоком, я думаю. Это будет так;

Set<Integer> h = new LinkedHashSet<>(Arrays.asList(1, 2, 3, 4, 6, 8, 9, 10));

    h.stream().anyMatch(isMissed -> {
        if (!h.contains(isMissed + 1)) {
            System.out.println(isMissed + 1);
            return true;
        }
        return false;
    });