Есть интересная задача: Поиск двух пропущенных чисел в массиве целых чисел

Есть интересная задача: есть массив целых чисел. Числа идут подряд от 1 до k. Но в
массиве пропущены два числа. Как найти эти числа?

Решил поделиться своим решением и реализацией (на Ruby) самого простого из них (еще два приведу в виде алгоритмов).

Способ 1.

Первое что приходит в голову — использовать индексы у массива.

Допустим у нас есть такой массив

enter_arr = [1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19]

Тогда индексы будут следовать от 0 до 16 включительно.
Очевидно воспользоваться разницей между значением массива и индексом.

1) Если число на своем месте, то разница будет 1
2) Если пропущено одно число, то значение в массиве сдвинется влево и разница будет 2
3) Если пропущены оба, то разница больше 2

Итак, идея проста, реализуем ее

# Способ 1. Воспользуемся индексом. Ищем разницу между индексом и значением.
class ArrFinder1
  def initialize(array_arg)
    @array_arg = array_arg
  end
  def array_each_helper arr, diff
    array_cut = []
    stopindex = -1
    stopnumber = -1
    arr.each_with_index do |elem,index|
        var = elem-index
          if var > diff
            stopindex = index; stopnumber = elem; break
          end
        array_cut << elem # обрезаем массив если надйено значение и пишем в него то что осталось
      end
    [stopindex, stopnumber, array_cut]
  end 
  def find_empty
    p "Input array:"
    p @array_arg

    stopindex1, stopnumber1, array_arg_cut =  array_each_helper(@array_arg, 2)
        
    # Смотрим, может пропущены 2 числа подряд
    if stopnumber1 - array_arg_cut[-1] == 3
      number1 = stopnumber1-1
      number2 = stopnumber1-2
    else
      number1 = @array_arg[stopindex1]-1
      stopindex2, stopnumber2 =  array_each_helper(array_arg_cut, 1)
      number2 = stopnumber2-1   
    end
        
    p "missing numbers:"
    p number1
    p number2   
  end   
end

Вызываем

obj = ArrFinder1.new enter_arr
obj.find_empty

Результат:

"Input array:"
[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19]
"missing numbers:"
12
3

Способ 2.

Однако решил усовершенствовать способ, обрезая массив пополам.

Алгоритм.
1) Выбираем середину массива и смотрим разницу в контрольной точке.
1.1) Если разница больше 2, значит пропущенные числа в первой половине.
1.2) Если равно 2, то пропущенное число 1 перед, другое после.
1.3) Если разница больше 1, то оба числа находятся дальше.
2) Если случай п.1.1, то берем первую половину массива и выбираем точку посередине и также смотрим значение разницы в ней. Далее смотрим как в п.1.1, 1.2, 1.3. Аналогично, если п.1.3, только берем вторую половину.
3) Если случай п.1.2 Выбираем середину массива первой половины и смотрим разницу в контрольной точке. Теперь уже смотрим разница больше ли 1. Если да, то повторяем п.3. Если нет то снова делим вторую часть и повторяем рекурсвивно действия как в начале пункта. До тех пор пока не найдем точку

Из преимуществ — нет необходимости пробегать весь массив, а сразу выбирать репперные точки. Что должно ускорить процесс. Также в данном подходе будет рекурсия, что упростит код.

Способ 3.

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

#0000 — ноля в задаче нет, но для наглядности напишу его тоже
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011
и т.д.

Как видим нам нужны первые два разряда числа.
Первый разряд идет последовательно 0-1-0-1, второй 0-0-1-1
Итак, если число пропущено, то будет смещение. Например, пропущено 2, тогда последовательность первого разряда (ноль тоже включу) 0-1-1-0, второго 0-0-1-0.
Таким образом несложно определить какое число пропущено.
Если пропущены 2 подряд, то смещение первого разряда не произойдет, но мы по смещению второго определим сдвиг: 0-0-0-0

Какие еще есть рациональные способы на Ваш взгляд?

Автор: Jeket