algorithm - цифру - тест вставьте пропущенное число 1 4 16




Вопрос с легким собеседованием усложнился: с учетом номеров 1..100, найдите недостающее число(и) (20)

Некоторое время назад у меня был интересный собеседование. Вопрос начался очень просто:

Q1 : У нас есть сумка с номерами 1 , 2 , 3 , ..., 100 . Каждое число появляется ровно один раз, поэтому 100 номеров. Теперь из мешка случайно выбрано одно число. Найдите недостающее число.

Я слышал этот вопрос перед интервью, конечно, поэтому я очень быстро ответил так:

A1 : Ну, сумма чисел 1 + 2 + 3 + … + N равна (N+1)(N/2) (см. Википедию: сумма арифметических рядов ). При N = 100 сумма равна 5050 .

Таким образом, если все числа присутствуют в сумке, сумма будет ровно 5050 . Поскольку отсутствует один номер, сумма будет меньше этого, а разница - это число. Таким образом, мы можем найти это недостающее число в O(N) времени и O(1) пространстве.

В этот момент я думал, что все пошло хорошо, но внезапно вопрос обернулся неожиданным поворотом:

Q2 : Это правильно, но теперь, как бы вы это сделали, если нет двух цифр?

Я никогда раньше не видел / не слышал / не рассматривал этот вариант, поэтому я запаниковал и не мог ответить на вопрос. Интервьюер настаивал на том, чтобы узнать мой мыслительный процесс, поэтому я упомянул, что, возможно, мы сможем получить дополнительную информацию, сравнив его с ожидаемым продуктом или, возможно, сделав второй проход после сбора некоторой информации с первого прохода и т. Д., Но я действительно просто снимал в темноте, а не на самом деле имеет четкий путь к решению.

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

Ответ интервьюера удивил меня: вы можете обобщить технику, чтобы найти 3 недостающих числа. Фактически, вы можете обобщить его, чтобы найти k недостающих чисел.

Qk : Если в сумме не хватает k чисел, как бы вы нашли это эффективно?

Это было несколько месяцев назад, и я до сих пор не мог понять, что это за техника. Очевидно, что существует нижняя граница времени Ω(N) так как мы должны сканировать все числа хотя бы один раз, но интервьюер настаивал на том, что сложность решения метода TIME и SPACE (за вычетом времени O(N) ) определяется в k не N.

Итак, вопрос здесь прост:

  • Как бы вы решили Q2 ?
  • Как бы вы решили Q3 ?
  • Как бы вы решили Qk ?

Разъяснения

  • Обычно есть N чисел от 1 .. N , а не только 1..100.
  • Я не ищу очевидное решение на основе набора, например, используя бит-набор , кодируя присутствие / отсутствие каждого номера на значение назначенного бита, поэтому используя O(N) бит в дополнительном пространстве. Мы не можем позволить себе дополнительное пространство, пропорциональное N.
  • Я также не ищу очевидного подхода первого рода. Этот и основанный на наборе подход заслуживают упоминания в интервью (их легко реализовать, и в зависимости от N может быть очень практичным). Я ищу решение Holy Grail (которое может быть или не быть практичным для реализации, но все же имеет желаемые асимптотические характеристики).

Итак, опять же, конечно, вы должны сканировать входные данные в O(N) , но вы можете записывать только небольшой объем информации (определенный в терминах k не N ), и затем должны как-то найти k недостающих чисел.


Вот краткое описание link Димитриса Андреу .

Помните сумму i-й степени, где i = 1,2, ..., k. Это сводит задачу к решению системы уравнений

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Используя тождества Ньютона , знание b i позволяет вычислить

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Если вы разложите многочлен (xa 1 ) ... (xa k ), коэффициенты будут точно c 1 , ..., c k - см . Формулы Viète . Так как каждое многочленов однозначно (кольцо многочленов является евклидовой областью ), это означает, что a i однозначно определяется с точностью до перестановки.

Это завершает доказательство того, что запоминания полномочий достаточно для восстановления чисел. Для константы k это хороший подход.

Однако, когда k меняется, прямой подход вычисления c 1 , ..., c k является чрезмерно дорогостоящим, так как, например, c k является произведением всех недостающих чисел, величина n! / (Nk) !. Чтобы преодолеть это, выполните вычисления в поле Z q , где q - простое число, такое, что n <= q <2n - оно существует по постулату Бертранда . Доказательство не нужно менять, поскольку формулы все еще сохраняются, а факторизация многочленов по-прежнему уникальна. Вам также нужен алгоритм факторизации над конечными полями, например, Berlekamp или Cantor-Zassenhaus .

Псевдокод высокого уровня для константы k:

  • Вычисление i-й степени заданных чисел
  • Вычитаем для получения сумм i-й степени неизвестных чисел. Вызвать суммы b i .
  • Используйте тождества Ньютона для вычисления коэффициентов из b i ; назовите их c i . В основном, c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 ) / 2; см. Википедию для точных формул
  • Коэффициент полинома x k -c 1 x k-1 + ... + c k .
  • Корнями многочлена являются необходимые числа a 1 , ..., a k .

Для изменения k найдите простое n <= q <2n, используя, например, Miller-Rabin, и выполните шаги со всеми числами, приведенными по модулю q.

Как прокомментировал Генрих Апфельмус, вместо простого q вы можете использовать q = 2 ⌈log n⌉ и выполнить арифметику в конечном поле .


Вот решение, которое использует k бит дополнительного хранилища, без каких-либо умных трюков и просто. Время выполнения O (n), дополнительное пространство O (k). Просто чтобы доказать, что это можно решить, не прочитав сначала решение или не гений:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= odd) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = even; i < n; ++i) data [i] += 1;
}

Как отметил @j_random_hacker, это очень похоже на поиск дубликатов в O (n) времени и O (1) пространстве , и здесь также работает адаптация моего ответа.

Предполагая, что «сумка» представлена ​​1-основанной матрицей A[] размера N - k , мы можем решить Qk в O(N) время и O(k) дополнительное пространство.

Во-первых, мы расширяем наш массив A[] на k элементов, так что теперь он имеет размер N Это дополнительное пространство O(k) . Затем мы запускаем следующий алгоритм псевдокода:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

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

Второй цикл переставляет расширенный массив так, что если элемент x присутствует хотя бы один раз, то одна из этих записей будет находиться в позиции A[x] .

Обратите внимание, что хотя он имеет вложенный цикл, он все еще работает в O(N) времени - swap происходит только тогда, когда существует i , так что A[i] != i , и каждая подкачка устанавливает по крайней мере один элемент такой, что A[i] == i , где раньше это было неверно. Это означает, что общее количество свопов (и, следовательно, общее количество исполнений тела цикла while) не превышает N-1 .

Третий цикл печатает те индексы массива i , которые не заняты значением i - это означает, что i должно быть, отсутствовал.


Можете ли вы проверить, существует ли каждый номер? Если да, вы можете попробовать следующее:

S = сумма всех чисел в сумке (S <5050)
Z = сумма недостающих чисел 5050 - S

если отсутствующие номера xи yзатем:

x = Z - y и
max (x) = Z - 1

Таким образом, вы проверяете диапазон от 1до max(x)и находите номер


Не уверен, если это наиболее эффективное решение, но я бы перебирал все записи и использовал битовый набор, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит.

Мне нравятся простые решения - и я даже верю, что это может быть быстрее, чем вычисление суммы или суммы квадратов и т. Д.


Подождите минуту. Как говорится в этом вопросе, в сумке насчитывается 100 номеров. Независимо от того, насколько велика k, проблема может быть решена в постоянное время, потому что вы можете использовать набор и удалять числа из набора не более 100 k итераций цикла. 100 постоянна. Набор оставшихся номеров - ваш ответ.

Если мы обобщаем решение чисел от 1 до N, ничего не меняется, кроме того, что N не является константой, поэтому мы находимся в O (N - k) = O (N) времени. Например, если мы используем бит-набор, мы устанавливаем биты в 1 в O (N) времени, итератируем по номерам, устанавливаем биты в 0 по мере продвижения (O (Nk) = O (N)), а затем мы есть ответ.

Мне кажется, что интервьюер спрашивал, как распечатать содержимое окончательного набора в O (k), а не O (N). Понятно, что с битовым набором вам нужно выполнить итерацию по всем N битам, чтобы определить, следует ли печатать номер или нет. Однако, если вы измените способ реализации набора, вы можете распечатать номера в k итерациях. Это делается путем помещения чисел в объект, который будет храниться как в хеш-наборе, так и в дважды связанном списке. Когда вы удаляете объект из набора хэшей, вы также удаляете его из списка. Ответы будут оставлены в списке, который теперь имеет длину k.


Чтобы решить вопрос с 2 (и 3) отсутствующими номерами, вы можете изменить quickselect , который в среднем работает в O(n) и использует постоянную память, если разделение выполняется на месте.

  1. Разделим множество относительно случайного стержня p на разбиения l , содержащие числа, меньшие, чем ось вращения, и r , которые содержат числа, большие, чем точка поворота.

  2. Определите, в каких разделах 2 числа отсутствуют, сравнивая значение поворота с размером каждого раздела ( p - 1 - count(l) = count of missing numbers in l и n - count(r) - p = count of missing numbers in r )

  3. a) Если в каждом разделе отсутствует одно число, используйте разницу суммарного подхода, чтобы найти каждое недостающее число.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 и ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) Если один раздел отсутствует, оба номера и раздел пуст, то недостающие номера являются либо (p-1,p-2) либо (p+1,p+2) зависимости от того, какой раздел отсутствует.

    Если в одном разделе отсутствует 2 числа, но не пуст, перезапишите на эту часть.

Имея всего 2 недостающих числа, этот алгоритм всегда отбрасывает хотя бы один раздел, поэтому он сохраняет среднюю временную сложность O(n) quickselect. Аналогично, с 3 недостающими числами этот алгоритм также отбрасывает по крайней мере один раздел с каждым проходом (поскольку, как и в случае с двумя отсутствующими номерами, максимум 1 раздел будет содержать несколько недостающих чисел). Тем не менее, я не уверен, насколько производительность уменьшается при добавлении лишних номеров.

Вот реализация, которая не использует локальное разбиение на разделы, поэтому этот пример не соответствует требованиям к пространству, но он иллюстрирует шаги алгоритма:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo


Я не проверял математику, но я подозреваю, что вычисление Σ(n^2) в тот же проход, что и мы вычисляем Σ(n) , предоставит достаточную информацию, чтобы получить два недостающих числа, Do Σ(n^3) если их три, и так далее.


Вам, вероятно, понадобится разъяснение того, что означает O (k).

Вот тривиальное решение для любого k: для каждого v в вашем наборе чисел накапливайте сумму 2 ^ v. В конце, цикл i от 1 до N. Если сумма по модулю 2 ^ i равна нулю, то i отсутствует.

Легко, правда? O (N), O (1) хранения и поддерживает произвольные k.

За исключением того, что вы вычисляете огромные числа, которые на реальном компьютере потребуют пространство O (N). Фактически, это решение идентично битовому вектору.

Таким образом, вы можете быть умными и вычислить сумму и сумму квадратов и сумму кубов ... вплоть до суммы v ^ k и сделать фантастическую математику для извлечения результата. Но это тоже большие числа, что вызывает вопрос: о какой абстрактной модели операции мы говорим? Сколько подходит в O (1) пространстве и сколько времени требуется, чтобы суммировать номера любого размера, который вам нужен?


Вы можете решить Q2, если у вас есть сумма обоих списков и продукт обоих списков.

(l1 - оригинал, l2 - измененный список)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Мы можем оптимизировать это, так как сумма арифметического ряда в n раз превышает среднее значение первого и последнего членов:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Теперь мы знаем, что (если a и b - удаленные числа):

a + b = d
a * b = m

Поэтому мы можем перестроить:

a = s - b
b * (s - b) = m

И размножайтесь:

-b^2 + s*b = m

И переставьте так, чтобы правая сторона была равна нулю:

-b^2 + s*b - m = 0

Тогда мы можем решить с помощью квадратичной формулы:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Пример кода Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Я не знаю сложность функций sqrt, сокращения и суммирования, поэтому я не могу решить сложность этого решения (если кто-нибудь знает, пожалуйста, прокомментируйте ниже).


Еще один способ - использовать остаточную фильтрацию графа.

Предположим, что числа с номерами 1 - 4 и 3 отсутствуют. Бинарное представление выглядит следующим образом:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

И я могу создать поток-график, как показано ниже.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Обратите внимание, что график потока содержит х узлов, а х - количество бит. Максимальное количество ребер (2 * x) -2.

Таким образом, для 32-битного целого будет занимать пространство O (32) или O (1).

Теперь, если я удаляю емкость для каждого числа, начиная с 1,2,4, тогда я остаюсь с остаточным графом.

0 ----------> 1 ---------> 1

Наконец, я буду запускать цикл следующим образом:

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Теперь результат resultсодержит числа, которые также отсутствуют (ложноположительный). Но k <= (размер результата) <= n, когда kотсутствуют элементы.

Я перейду через данный список в последний раз, чтобы отметить результат, отсутствующий или нет.

Таким образом, временной сложностью будет O (n).

Наконец, можно уменьшить число ложноположительных (и пространство , необходимое), принимая узлы 00, 01, 11, 10вместо того , чтобы просто 0и 1.


Может быть, этот алгоритм может работать для вопроса 1:

  1. Предкоммутировать xor первых 100 целых чисел (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. xor элементы, поскольку они продолжают поступать из входного потока (val1 = val1 ^ next_input)
  3. окончательный ответ = val ^ val1

Или еще лучше:

def GetValue(A)
    for i=1 to 100
     do
       val=val^i
     done
     for value in A:
       do
         val=val^value 
       done
    return val

На самом деле этот алгоритм можно разложить на два недостающих числа. Первый шаг остается тем же. Когда мы вызываем GetValue с двумя пропущенными номерами, результатом будет a a1^a2- два недостающих числа. Давайте скажем

val = a1^a2

Теперь, чтобы вычесть a1 и a2 из val, мы берем любой бит в val. Допустим, ithбит установлен в val. Это означает, что a1 и a2 имеют разную четность в ithбитовой позиции. Теперь мы делаем еще одну итерацию в исходном массиве и сохраняем два значения xor. Один для чисел, которые имеют i-й бит, и другие, у которых нет i-го битового набора. Теперь у нас есть два ведра чисел, и он a1 and a2будет гарантирован, что будет в разных ведрах. Теперь повторите то же самое, что мы сделали для поиска одного отсутствующего элемента в каждом из ковша.


У меня есть идея, но это предполагает, что фактический размер массива равен 100, а недостающие числа заменяются чем-то другим (например, -1).

В принципе, сделайте вид, который является измененной версией сортировки, которая меняет местами на месте. Я считаю, что это O (n) время (исправьте меня, если я ошибаюсь), потому что мы используем тот факт, что мы уже знаем числа, которые должны существовать. Мы меняем значение с «правильной» позицией, пока индекс, на котором мы находимся, имеет правильное число (или имеет -1).

После того, как мы закончим с этим, мы просто зацикливаем список снова, и индекс будет в основном отсутствующими числами

#Set up the input
input = (1..100).to_a.shuffle
input[rand(0..99)] = -1
input[rand(0..99)] = -1

def f(a)
  for i in 0..99
    while (a[i] != i+1) && a[i] > 0
      v1 = a[i]
      v2 = a[v1 - 1]
      a[i] = v2
      a[v1 - 1] = v1
    end
  end

  result = []
  a.each_with_index do |value, index|
    if value < 0
      result.push(index + 1)
    end
  end

  return result
end

#Returns the 2 missing numbers
puts f(input)

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

Итак, поскольку вы видите все цифры, просто найдите номер, который отсутствует. То же самое происходит, когда отсутствуют два числа. Довольно просто, я думаю. Нет смысла использовать уравнение, когда вы увидите цифры, оставшиеся в сумке.


Я не знаю, эффективна она или нет, но я хотел бы предложить это решение.

  1. Вычислить xor из 100 элементов
  2. Вычислить xor из 98 элементов (после удаления двух элементов)
  3. Теперь (результат 1) XOR (результат 2) дает вам xor двух отсутствующих nos i..ea XOR b, если a и b являются отсутствующими элементами.
    4. Получите сумму отсутствующих Nos с вашим обычным подходом к sum diff diff и позволяет сказать, что diff - d.

Теперь запустите цикл, чтобы получить возможные пары (p, q), оба из которых лежат в [1, 100] и суммируются с d.

Когда получается пара, проверьте, является ли (результат 3) XOR p = q, и если да, мы закончили.

Пожалуйста, исправьте меня, если я ошибаюсь, а также прокомментируйте временную сложность, если это правильно


Вы можете мотивировать решение, думая об этом с точки зрения симметрии (группы, в математическом языке). Независимо от порядка набора чисел, ответ должен быть таким же. Если вы собираетесь использовать kфункции, чтобы помочь определить недостающие элементы, вы должны думать о том, какие функции имеют это свойство: симметричное. Функция s_1(x) = x_1 + x_2 + ... + x_nявляется примером симметричной функции, но есть и другие более высокой степени. В частности, рассмотрим элементарные симметрические функции . Элементарная симметричная функция степени 2 является s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nсуммой всех произведений двух элементов. Аналогично для элементарных симметричных функций степени 3 и выше. Они, очевидно, симметричны. Кроме того, оказывается, что они являются строительными блоками для всех симметричных функций.

Вы можете построить элементарные симметричные функции, указав это s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Дальнейшая мысль должна убедить вас в этом s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))и так далее, чтобы их можно было вычислить за один проход.

Как узнать, какие элементы отсутствуют в массиве? Подумайте о полиноме (z-x_1)(z-x_2)...(z-x_n). Он оценивает, 0если вы введете любой из чисел x_i. Расширяя полином, вы получаете z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Здесь также появляются элементарные симметричные функции, что неудивительно, так как многочлен должен оставаться неизменным, если мы применяем любую перестановку к корням.

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

Наконец, если мы обеспокоены переполнением памяти большими числами (n-й симметричный многочлен будет иметь порядок 100!), мы можем сделать эти вычисления, mod pгде pпросто больше 100. В этом случае мы вычисляем многочлен mod pи находим, что он снова оценивает чтобы , 0когда вход представляет собой число в наборе, и она вычисляется в ненулевое значение , когда вход числа , не в наборе. Однако, как указывали другие, чтобы получить значения из полинома во времени, зависящие от k, а не N, мы должны умножить многочлен mod p.


Мы можем делать Q1 и Q2 в O (log n) большую часть времени.

Предположим, что наша memory chipсостоит из массива nчисла test tubes. И число xв пробирке представлено x milliliterхимико-жидкостью.

Предположим, что наш процессор является laser light. Когда мы зажигаем лазер, он пересекает все трубки перпендикулярно его длине. Каждый раз, когда он проходит через химическую жидкость, светимость уменьшается 1. И прохождение света на определенной отметке миллиметра - это операция O(1).

Теперь, если мы зажжем наш лазер в середине пробирки и получим светимость

  • равняется предварительно рассчитанному значению (вычисляется, когда номера отсутствуют), то недостающие числа больше n/2.
  • Если наш результат меньше, то есть хотя бы одно недостающее число, которое меньше n/2. Мы также можем проверить, уменьшена ли светимость на 1или 2. если он будет уменьшен к тому времени, 1то недостающее число меньше, n/2а другое больше n/2. Если он уменьшится к тому времени, 2то оба числа будут меньше n/2.

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

Параллельные алгоритмы, которые стоит упомянуть (потому что они интересны),

  • сортировка по некоторому параллельному алгоритму, например, параллельное слияние может быть выполнено во O(log^3 n)времени. И тогда недостающее число может быть найдено двоичным поиском во O(log n)времени.
  • Теоретически, если у нас есть nпроцессоры, каждый процесс может проверить один из входов и установить некоторый флаг, который идентифицирует число (удобно в массиве). И на следующем шаге каждый процесс может проверять каждый флаг и, наконец, выводить число, которое не помечено. Весь процесс займет O(1)время. Он имеет дополнительное O(n)пространство / память.

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


Очень хорошая проблема. Я бы воспользовался набором разностей для Qk. Многие языки программирования даже поддерживают его, как в Ruby:

missing = (1..100).to_a - bag

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


Я бы взял другой подход к этому вопросу и исследовал интервьюера для получения более подробной информации о более крупной проблеме, которую он пытается решить. В зависимости от проблемы и требований, связанных с ней, очевидное решение на основе набора может быть правильным, а метод generate-a-list-and-pick-through-it-afterward может и не быть.

Например, может случиться так, что интервьюер собирается отправлять nсообщения и должен знать, kчто это не привело к ответу, и ему нужно знать его как можно меньше настенных часов после того, как nkпоступит ответ. Давайте также скажем, что природа канала сообщений такова, что даже работает на полном расстоянии, есть достаточно времени, чтобы сделать некоторую обработку между сообщениями, не оказывая никакого влияния на то, сколько времени потребуется, чтобы получить конечный результат после того, как последний ответ поступит. Это время можно использовать для вставки некоторого идентифицирующего аспекта каждого отправленного сообщения в набор и удаления его по мере поступления каждого соответствующего ответа. Как только последний ответ пришел, единственное, что нужно сделать, это удалить его идентификатор из набора, который в типичных реализацияхO(log k+1), После этого набор содержит список kотсутствующих элементов и дополнительной обработки не требуется.

Это, конечно, не самый быстрый подход для пакетной обработки предварительно сгенерированных пакетов чисел, потому что все это работает O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Но он работает для любого значения k(даже если оно неизвестно заранее), а в приведенном выше примере оно применялось таким образом, чтобы минимизировать самый критический интервал.


Я думаю, что это можно сделать без каких-либо сложных математических уравнений и теорий. Ниже приведено предложение о решении проблемы временной сложности O (2n):

Предположения входной формы:

# номеров в сумке = n

# недостающих чисел = k

Числа в сумке представлены массивом длины n

Длина входного массива для algo = n

Отсутствующие записи в массиве (числа, выведенные из мешка) заменяются значением первого элемента массива.

Например. Первоначально сумка выглядит как [2,9,3,7,8,6,4,5,1,10]. Если вынуть 4, значение 4 станет 2 (первый элемент массива). Поэтому после взятия 4 из мешка будет выглядеть как [2,9,3,7,8,6,2,5,1,10]

Ключом к этому решению является пометка INDEX посещаемого номера путем отрицания значения в этом INDEX по мере прохождения массива.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }




math