Вопрос по algorithm, math, c++ – Найти два пропущенных номера

10

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

@jpalecek Это не дубликат. ОП сказал (в комментарии), что числа не находятся в диапазоне. sepp2k
Извините, я тоже не могу вспомнить цифры. Cody Gray♦
@Shedal Предположительно, это означает «постоянный объем памяти». sepp2k
это невозможно с O (1) памятью. Karoly Horvath
числа должны быть сериями? [1, ...., n] а вам нужно найти недостающий элемент? amit

Ваш Ответ

6   ответов
0

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

Решение здесь

2

как только я закончил читать вопрос. Но ответы выше предполагают, что это невозможно с O (1) памятью или что должно быть ограничение на диапазон чисел. Скажите мне, если мое понимание вопроса неверно. Хорошо, вот так

У тебя естьO(1) память - что означает, что у вас естьconstant amount of memory.

Когдаn числа передаются вам в первый раз, просто продолжайте добавлять их в одну переменную и продолжайте умножать их в другую. Таким образом, в конце 1-го прохода у вас есть сумма и произведение всех чисел в 2 переменныхS1 а такжеP1, Вы использовали 2 переменные до сих пор (+1, если вы читаете числа в памяти).

Когда(n-2) номера передаются вам во второй раз, сделайте то же самое. Сохраните сумму и произведение(n-2) числа в 2 других переменныхS2 а такжеP2, Вы использовали 4 переменные до сих пор (+1, если вы читаете числа в памяти).

Если два пропущенных числаx а такжеy, затем

x + y = S1 - S2
x*y = P1/P2;

У вас есть два уравнения в двух переменных. Решите их.

Таким образом, вы использовали постоянный объем памяти (независимо от n).

Error: User Rate Limit ExceededO(1)Error: User Rate Limit ExceedednError: User Rate Limit Exceededn!Error: User Rate Limit ExceededO(log(n!)) = O(nlogn)Error: User Rate Limit Exceeded
1
void Missing(int arr[], int size)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  int n = size - 2;
  int x = 0, y = 0;

  /* Get the xor of all elements in arr[] and {1, 2 .. n} */
  for(i = 1; i < size; i++)
    xor ^= arr[i];  
  for(i = 1; i <= n; i++)
    xor ^= i;   

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < size; i++)
  {
    if(arr[i] & set_bit_no)
      x = x ^ arr[i]; /*XOR of first set in arr[] */
    else
      y = y ^ arr[i]; /*XOR of second set in arr[] */
  }
  for(i = 1; i <= n; i++)
  {
    if(i & set_bit_no)
      x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
    else
      y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
  }

  printf("\n The two repeating missing elements are are %d & %d ", x, y);
}
11

It can be done with O(1) memory.

Вам нужно только несколько целых чисел, чтобы отслеживать некоторые текущие суммы. Целые числа не требуют log n битов (где n - количество входных целых чисел), им требуется только 2b + 1 бит, где b - количество бит в отдельном входном целом числе.

Когда вы впервые прочитаете поток, добавьте все числа и все их квадраты, то есть для каждого входного числа n, сделайте следующее:

sum += n
sq_sum += n*n

Затем во втором потоке сделайте то же самое для двух разных значений, sum2 и sq_sum2. Теперь сделайте следующую математику:

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

Вам нужно 2b + 1 бит во всех промежуточных результатах, потому что вы храните произведения двух входных целых чисел и в одном случае умножаете одно из этих значений на два.

Error: User Rate Limit ExceededO(1)Error: User Rate Limit ExceededO(1)Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded amin k
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceedednError: User Rate Limit ExceededlognError: User Rate Limit ExceededO(logn)Error: User Rate Limit Exceededb itself is linear in lognError: User Rate Limit Exceededthe numbers are not necesseraly from a certain rangeError: User Rate Limit ExceededO(1)Error: User Rate Limit Exceeded
3

It cannot be done with O(1) memory.

Предположим, у вас есть постояннаяk биты памяти - тогда вы можете иметь2^k возможные состояния для вашего алгоритма.

Однако - вход не ограничен, и предположим, что есть(2^k) + 1 возможные ответы на(2^k) + 1 разные проблемные случаи, отпринцип пирогона, вы вернете один и тот же ответ дважды для 2 задач с разными ответами, и, следовательно, ваш алгоритм неверен.

Error: User Rate Limit Exceededp(n)Error: User Rate Limit Exceeded2^p(n)Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
3

что числа находятся в диапазоне от 1..N и 2 из них отсутствуют -x а такжеyВы можете сделать следующее:

Используйте формулу Гаусса:sum = N(N+1)/2

sum - actual_sum = x + y

Используйте произведение чисел:product = 1*2..*N = N!

product - actual_product = x * y

Решите x, y, и у вас есть пропущенные числа.

Короче говоря - пройдитесь по массиву и суммируйте каждый элемент, чтобы получитьactual_sum, умножьте каждый элемент, чтобы получитьactual_product, Затем решите два уравнения дляx y.

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceedednError: User Rate Limit ExceededlognError: User Rate Limit Exceeded
Error: User Rate Limit ExceededmeantError: User Rate Limit Exceeded
Error: User Rate Limit ExceededcError: User Rate Limit ExceededNError: User Rate Limit Exceededc*f(n)Error: User Rate Limit ExceedednError: User Rate Limit Exceededn > NError: User Rate Limit ExceededO(f(n)).
Error: User Rate Limit Exceeded

Похожие вопросы