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

Ответ 1

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

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

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

Сумма (фактическая) = N (N + 1)/2 + k - j

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

k = Сумма (фактическая) -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.

Ответ 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 отсутствует.

• Найти три числа, которые появляются только один раз, что составляет около трех.

Ответ 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);

Ответ 4

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

и

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

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

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

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

Ответ 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

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

Ответ 6

Вот реализация 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;
}

Ответ 7

Код 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)