Найти недостающие и повторяющиеся элементы в массиве в линейном времени и постоянном пространстве

Question

Вам дан массив N 64-битных целых чисел. N может быть очень большим. Вы знаете, что каждое целое число 1..N появляется в массиве один раз, за ​​исключением того, что отсутствует одно целое число и дублируется одно целое.

Напишите линейный алгоритм времени, чтобы найти пропущенные и дублированные числа. Кроме того, ваш алгоритм должен работать в небольшом постоянном пространстве и оставить массив без изменений.

Источник: http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

Answer 1

Если бы все числа присутствовали в массиве, сумма была бы N(N+1)/2.

Определите фактическую сумму, суммируя все числа в массиве в O (n), пусть это будет Sum(Actual).

Отсутствует одно число, пусть это будет j, а однономер дублируется, пусть это будет k.Это означает, что

Sum (Actual) = N (N + 1) / 2 + k - j

, полученное из этого

k = Sum (Actual) -N (N + 1) / 2 + j

Также мы можем вычислить сумму квадратов в массиве, которая бы суммировала до n ³ / 3 + n ² / 2 + n / 6, если все числа присутствовали.

Теперь мы можем вычислить фактическую сумму квадратов в O (n), пусть это будет Sum(Actual Squares).

Сумма (фактические квадраты) = n ³ / 3 + n ² / 2 + n / 6 + k ² - j ²

Теперь у нас есть два уравнения, с помощью которых мы можем определить j и k.

Answer 2

Трюк XOR работает в два прохода с массивом только для чтения.

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

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

XOR всех элементов массива вместе с 1,2,...,N.

Результат w = x XOR y.

Теперь, поскольку x и y различны, w не равен нулю.

Выберите любой ненулевой бит w. x и y отличаются этим битом. Скажем, позиция бита k.

Теперь рассмотрим разбиение массива (и чисел 1,2,...,N) на два набора в зависимости от того, равен ли бит в позиции k 0 или 1.

Теперь, если мы вычислим XOR (отдельно) элементов двух наборов, результат должен быть x и y.

Поскольку критерием разделения является просто проверка, установлен ли бит или нет, мы можем вычислить два XOR из двух наборов, сделав еще один проход через массив и имея две переменные, каждая из которых содержит XOR элементов видел до сих пор (и 1,2,...N), для каждого набора. В конце, когда мы закончим, эти две переменные будут содержать x и y.

Похожие:

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

• Найти три числа, появившиеся только один раз , что примерно равно трем пропущенным.

Answer 3

Используя основную идею из вопроса об интервью , вы можете сделать:

• Суммируйте все числа (назовем это S1) и их квадраты (S2)
• Вычислить ожидаемую сумму чисел без изменений, т.е. E1 = n*(n+1)/2 и E2 = n*(n+1)*(2n+1)/6
• Теперь вы знаете, что E1 - S1 = d - m и E2 - S2 = d^2 - m^2, где d - дублированный номер, а m - отсутствующий.

• Решите эту систему уравнений, и вы обнаружите, что:

  m = 1/2 ((E2 - S2)/(E1 - S1) - (E1 - S1))
  d = 1/2 ((E2 - S2)/(E1 - S1) + (E1 - S1)) // or even simpler: d = m + (E1 - S1)
  

.

$S1 = $S2 = 0;
foreach ($nums as $num) {
    $S1 += $num;
    $S2 += $num * $num;
}

$D1 = $n * ($n + 1) / 2                - $S1;
$D2 = $n * ($n + 1) * (2 * $n + 1) / 6 - $S2;

$m = 1/2 * ($D2/$D1 - $D1);
$d = 1/2 * ($D2/$D1 + $D1);

Answer 4

Вот реализация Java, основанная на идее @Aryabhatta:
Ввод: [3 1 2 5 3]
Выход: [3, 4]

public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
    ArrayList<Integer> ret = new ArrayList<>();
    int xor = 0, x = 0, y = 0;
    for(int i=0; i<A.size(); i++) {
        xor ^= A.get(i);
    }
    for(int i=1; i<=A.size(); i++) {
        xor ^= i;
    }

    int setBit = xor & ~(xor-1);
    for(int i=0; i<A.size(); i++) {
        if((A.get(i) & setBit) != 0) {
            x ^= A.get(i);
        } else {
            y ^= A.get(i);
        }
    }
    for(int i=1; i<=A.size(); i++) {
        if((i & setBit) != 0) {
            x ^= i;
        } else {
            y ^= i;
        }
    }

    for(int i=0; i<A.size(); i++) {
        if(A.get(i) == x) {
            ret.add(x);
            ret.add(y);
            return ret;
        } 

        if(A.get(i) == y) {
            ret.add(y);
            ret.add(x);
            return ret;
        }
    }

    return ret;
}

Answer 5

Буквально принимая требование leave the array untouched (то есть массив может быть временно изменен, если он не изменяется в конце), можно предложить решение, ориентированное на программирование.

Я предполагаю, что размер массива N намного меньше, чем 2 ^ 64 , что является совершенно нереалистичным объемом памяти. Поэтому можно смело предположить, что N < 2^P такое, что P << 64 (значительно меньше). Другими словами, это означает, что все числа в массиве имеют некоторые старшие неиспользованные биты . Так что давайте просто используем старший бит в качестве флага, был ли индекс этой позиции виден в массиве. Алгоритм работает следующим образом:

 set HIGH = 2^63  // a number with only the highest bit set
 scan the array, for each number k do
   if array[k] < HIGH: array[k] = array[k] + HIGH // set the highest bit
   else: k is the duplicate
 for each i in 1..N do
   if array[i] < HIGH: i is missing
   else: array[i] = array[i] - HIGH // restore the original number

Это линейное время и очень мало вычислений

Answer 6

Решение, предложенное BrokenGlass, охватывает случай двух неизвестных (соответствует одному дублирующему номеру и одному отсутствующему номеру) с использованием двух формул:

и

Формулы дают обобщенное число гармоник порядков n от -1 и -2 соответственно.(Степенные ряды)

Это решение обобщается на 3 неизвестных путем включения значения обобщенного номера гармоники порядка n, равного -3.

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

---

Морон отмечает, что этот подход обсуждался ранее в StackOverflow в Простой вопрос для интервью стал сложнее .

Answer 7

    long long int len = A.size();
    long long int sumOfN = (len * (len+1) ) /2, sumOfNsq = (len * (len +1) *(2*len +1) )/6;
    long long int missingNumber1=0, missingNumber2=0;

    for(int i=0;i<A.size(); i++){
       sumOfN -= (long long int)A[i];
       sumOfNsq -= (long long int)A[i]*(long long int)A[i];
    }

    missingno = (sumOfN + sumOfNsq/sumOfN)/2;
    reaptingNO = missingNumber1 - sumOfN;

Answer 8

Код Psuedo при условии, что набор отсортирован

missing = nil
duplicate = nil

for i = 0, i < set.size - 1, i += 1
  if set[i] == set[i + 1]
    duplicate = set[i]
  else if((set[i] + 1) != set[i+1])
    missing = set[i] + 1
  if missing != nil && duplicate != nil
    break

return (missing, duplicate)