Простой вопрос интервью усложнился: по номерам 1..100 найдите пропущенные числа, по которым точно k отсутствуют

Question

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

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

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

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

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

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

Q2 : Это правильно, но как теперь это сделать, если пропущено TWO номеров?

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

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

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

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

Это было несколько месяцев назад, и я до сих пор не могу понять, что это за техника.Очевидно, существует нижняя граница времени Ω(N), поскольку мы должны отсканировать все числа хотя бы один раз, но интервьюер настаивал на сложности ВРЕМЯ и ПРОСТРАНСТВО сложности метода решения (минус O(N) время сканирования сканирования) определяется в k не N .

Так что вопрос здесь прост:

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

---

Пояснения

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

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

Answer 1

Ключ заключается в использовании индексов для отметки, если число присутствует или не находится в диапазоне. Здесь мы знаем, что у нас есть 1 к N. Временная сложность O (n) Пространственная сложность O (1)

Последующие вопросы: Это может быть изменено, чтобы найти, отсутствует ли элемент в AP разности d. Другой вариант может включать в себя поиск первого отсутствующего + ve числа из любого случайного массива, также содержащего -ve число. Затем сначала раздел вокруг 0 ​​ быстрая сортировка , затем выполните эту процедуру на правой стороне раздела части массива , сделайте необходимые изменения.

public static void  missing(int [] arr){        
      for(int i=0; i< arr.length; i++){       
          if(arr[i]!=-1 && arr[i]<=arr.length){
              int idx=i;
              while(idx>=0 && idx<arr.length&& arr[idx]!=-1 ){
                   int temp =arr[idx];
                   // temp-1 because array index starts from 0, i.e a[0]=-1 is indicates that 1 is present in the array
                   arr[temp-1]=-1;
                   idx=temp-1;
              }
          }
      }
    }

После этого нам нужно перебрать массив и проверить, что a [i]! = - 1, тогда i + 1 - пропущенное число. Мы должны быть осторожны, когда [i]> N.

Answer 2

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

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

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

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

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

Answer 3

Если число появляется только один раз, это довольно легко определить следующим образом:

Создать логический массив, boolArray, размера данного числа;здесь оно равно 100.

Переберите входные числа и установите для элемента значение true в соответствии с числовым значением.Например, если найдено 45, тогда установите boolArray[45-1] = true;

Это будет операция O (N).

Затем выполните цикл boolArray.Если элемент остается ложным, то индекс элемента + 1 - это отсутствующее число.Например, если boolArray[44] равно false, мы знаем, что номер 45 отсутствует.

Это операция O (n).Сложность пространства равна O (1).

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

Answer 4

Это очень простой вопрос

void findMissing(){
    bool record[N] = {0};
    for(int i = 0; i < N; i++){
        record[bag[i]-1] = 1;
    }
    for(int i = 0; i < N; i++){
        if(!record[i]) cout << i+1 << endl;
    }
}

O (n) пространственно-временная сложность

Answer 5

Мы можем использовать следующий простой код для поиска повторяющихся и пропущенных значений:

    int size = 8;
    int arr[] = {1, 2, 3, 5, 1, 3};
    int result[] = new int[size];

    for(int i =0; i < arr.length; i++)
    {
        if(result[arr[i]-1] == 1)
        {
            System.out.println("repeating: " + (arr[i]));
        }
        result[arr[i]-1]++;
    }

    for(int i =0; i < result.length; i++)
    {
        if(result[i] == 0)
        {
            System.out.println("missing: " + (i+1));
        }
    }

Answer 6

Я думаю, что это можно обобщить так:

Обозначим S, M в качестве начальных значений для суммы арифметических рядов и умножения.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Я должен подумать о формуле, чтобы вычислить это, но это не главное. В любом случае, если отсутствует один номер, вы уже предоставили решение. Однако, если два числа отсутствуют, давайте обозначим новую сумму и общее кратное S1 и M1, которые будут следующими:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Поскольку вы знаете S1, M1, M и S, вышеприведенное уравнение разрешимо найти a и b, пропущенные числа.

Теперь для трех пропавших чисел:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

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

Answer 7

вы можете использовать бинарный поиск, чтобы найти интервалы пропущенных (или смежных) чисел. Время выполнения должно быть около (количество интервалов) * log (средняя длина интервала) * N. Полезно, если интервалов не много.

Answer 8

    //sort
    int missingNum[2];//missing 2 numbers- can be applied to more than 2
    int j = 0;    
    for(int i = 0; i < length - 1; i++){
        if(arr[i+1] - arr[i] > 1 ) {
            missingNum[j] = arr[i] + 1;
            j++;
        }
    }

Answer 9

Один из способов сделать это - вычислить по модулю простое число 101.

рассчитайте и сохраните произведение целых чисел от 1 до 100, уменьшите это число по модулю 101. Мало экзо: результат будет 1.

вычислить и сохранить сумму всех чисел от 1 до 100, уменьшить результат по модулю 101. Маленькая экзо: результат будет 0.

теперь предположим, что в сумке удалены номера x и y.

Рассчитайте произведение и сумму всего в сумке по модулю 101. Так что я буду знать значения

a = x + y и б = х * у

по модулю 101.

теперь легко найти x и y по модулю 101 (решить квадратичную поли над конечным полем из 101 элемента).

Теперь вы знаете x и y по модулю 101. но поскольку вы также знаете, что x и y меньше 101, вы знаете их истинные значения.

Answer 10

Отказ от ответственности: я читал этот вопрос в течение нескольких дней, но я не знаю, как понимать математику.

Я пытался решить его с помощью набора:

arr=[1,2,4,5,7,8,10] # missing 3,6,9
NMissing=3
arr_origin = list(range(1,arr[-1]+1))

for i in range(NMissing):
      arr.append(arr[-1]) ##### assuming you do not delete the last one

arr=set(arr)
arr_origin=set(arr_origin)
missing=arr_origin-arr # 3 6 9