Алгоритм поиска двух повторяющихся чисел в массиве без сортировки

Question

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

например. в {2, 3, 6, 1, 5, 4, 0, 3, 5} n = 9, а повторные числа равны 3 и 5.

Как лучше всего найти повторяющиеся числа?

P.S. [Вы не должны использовать сортировку]

Answer 1

Существует решение O (n) , если вы знаете, какова возможная область ввода. Например, если ваш входной массив содержит числа от 0 до 100, рассмотрите следующий код.

bool flags[100];
for(int i = 0; i < 100; i++)
    flags[i] = false;

for(int i = 0; i < input_size; i++)
    if(flags[input_array[i]])
         return input_array[i];
    else       
        flags[input_array[i]] = true;

Конечно, есть дополнительная память, но она самая быстрая.

Answer 2

ОК, кажется, я просто не могу дать ему отдохнуть :)

Самое простое решение

int A[N] = {...};

int signed_1(n) { return n%2<1 ? +n : -n;  } // 0,-1,+2,-3,+4,-5,+6,-7,...
int signed_2(n) { return n%4<2 ? +n : -n;  } // 0,+1,-2,-3,+4,+5,-6,-7,...

long S1 = 0;  // or int64, or long long, or some user-defined class
long S2 = 0;  // so that it has enough bits to contain sum without overflow

for (int i=0; i<N-2; ++i)
{
   S1 += signed_1(A[i]) - signed_1(i);
   S2 += signed_2(A[i]) - signed_2(i);
} 

for (int i=N-2; i<N; ++i)
{
   S1 += signed_1(A[i]);
   S2 += signed_2(A[i]);
} 

S1 = abs(S1);
S2 = abs(S2);

assert(S1 != S2);  // this algorithm fails in this case

p = (S1+S2)/2;
q = abs(S1-S2)/2;

Одна сумма (S1 или S2) содержит p и q с одинаковым знаком, другая сумма - с противоположными знаками, все остальные члены исключаются.
S1 и S2 должны иметь достаточно битов для размещения сумм, алгоритм не означает переполнение из-за abs ().

если abs (S1) == abs (S2), то алгоритм завершится неудачно, хотя это значение все равно будет разницей между p и q (то есть abs (p - q) == abs (S1)).

Предыдущее решение

Я сомневаюсь, что кто-нибудь когда-нибудь столкнется с такой проблемой в поле;)
и я думаю, я знаю ожидание учителя:

Давайте возьмем массив {0,1,2, ..., n-2, n-1},
Данный можно получить, заменив два последних элемента n-2 и n-1 неизвестными p и q (меньший порядок)

итак, сумма элементов будет (n-1) n / 2 + p + q - (n-2) - (n-1)
сумма квадратов (n-1) n (2n-1) / 6 + p ^ 2 + q ^ 2 - (n-2) ^ 2 - (n-1) ^ 2

Остается простая математика:

  (1)  p+q = S1  
  (2)  p^2+q^2 = S2

Конечно, вы не решите это, поскольку математические классы учат решать квадратные уравнения.

Сначала вычислим все по модулю 2 ^ 32, то есть допустим переполнение.
Затем проверьте пары {p, q}: {0, S1}, {1, S1-1} ... по выражению (2), чтобы найти кандидатов (их может быть больше 2 из-за модуляции и возведения в квадрат)
И, наконец, проверьте найденных кандидатов, если они действительно присутствуют в массиве дважды.

Answer 3

Вы знаете, что ваш массив содержит каждое число от 0 до n-3 и два повторяющихся (p & q). Для простоты давайте пока проигнорируем 0-регистр.

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

1 + 2 + ... + n-3 + p + q = p + q + (n-3)(n-2)/2

Таким образом, если вы вычтите (n-3) (n-2) / 2 из суммы всего массива, вы получите

sum(Array) - (n-3)(n-2)/2 = x = p + q

Теперь сделайте то же самое для продукта:

1 * 2 * ... * n - 3 * p * q = (n - 3)! * p * q

prod(Array) / (n - 3)! = y = p * q

Теперь у вас есть следующие условия:

x = p + q

y = p * q

=> y(p + q) = x(p * q)

Если вы преобразуете этот термин, вы сможете вычислить p и q

Answer 4

Возможно, вы сможете воспользоваться тем, что сумма (массив) = (n-2) * (n-3) / 2 + два пропущенных числа.

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

Answer 5

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

Answer 6

Проверьте эту старую, но хорошую статью по теме:

• Поиск повторяющихся элементов (PDF)

Answer 7

Некоторые ответы на вопрос: Алгоритм определения, содержит ли массив n… n + m? , содержащий в качестве подзадачи решения, которые вы можете принять для своих целей.

Например, вот соответствующая часть из моего ответа :

bool has_duplicates(int* a, int m, int n)
{
  /** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int')

      Whether a[] array has duplicates.

      precondition: all values are in [n, n+m) range.

      feature: It marks visited items using a sign bit.
  */
  assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN
  for (int *p = a; p != &a[m]; ++p) {
    *p -= (n - 1); // [n, n+m) -> [1, m+1)
    assert(*p > 0);
  }

  // determine: are there duplicates
  bool has_dups = false;
  for (int i = 0; i < m; ++i) {
    const int j = abs(a[i]) - 1;
    assert(j >= 0);
    assert(j < m);
    if (a[j] > 0)
      a[j] *= -1; // mark
    else { // already seen
      has_dups = true;
      break;
    }
  }

  // restore the array
  for (int *p = a; p != &a[m]; ++p) {
    if (*p < 0) 
      *p *= -1; // unmark
    // [1, m+1) -> [n, n+m)
    *p += (n - 1);        
  }

  return has_dups; 
}

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

Работает для массивов размером до INT_MAX (в 64-битных системах это 9223372036854775807).

Answer 8

Я знаю, что вопрос очень старый, но я неожиданно его задал и думаю, что у меня есть интересный ответ на него. Мы знаем, что это головоломка и тривиальное решение (т. Е. HashMap, Sort и т. Д.), Независимо от того, насколько хорошими они будут, скучно.

Поскольку числа являются целыми числами, они имеют постоянный размер в битах (т.е. 32). Предположим, мы сейчас работаем с 4-битными целыми числами. Мы ищем A и B , которые являются повторяющимися числами.

Нам нужно 4 сегмента, каждый на один бит. Каждый сегмент содержит числа, для которых его бит равен 1. Например, сегмент 1 получает 2, 3, 4, 7, ...:

Bucket 0 : Sum ( x where: x & 2 power 0 == 0 )
...
Bucket i : Sum ( x where: x & 2 power i == 0 )

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

Как только вышеупомянутые сегменты будут сгенерированы, группа из них будет иметь значения больше, чем ожидалось. Построив число из ведер, мы получим (A ИЛИ B для вашей информации).

Мы можем вычислить (A XOR B) следующим образом:

A XOR B = Array[i] XOR Array[i-1] XOR ... 0, XOR n-3 XOR n-2  ... XOR 0

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

Для сегментов, которые имеют только одно число, мы можем извлечь число num = (сумма - ожидаемая сумма сегмента). Тем не менее, мы должны быть хорошими, только если мы сможем найти одно из дублирующих чисел, поэтому, если у нас есть хотя бы один бит в A XOR B, у нас есть ответ.

Но что, если A XOR B равен нулю? Ну, этот случай возможен только в том случае, если оба повторяющихся числа - это одно и то же число, и тогда наш номер является ответом А ИЛИ Б.

Answer 9

suppose array is

a[0], a[1], a[2] ..... a[n-1]

sumA = a[0] + a[1] +....+a[n-1]
sumASquare = a[0]*a[0] + a[1]*a[1] + a[2]*a[2] + .... + a[n]*a[n]

sumFirstN = (N*(N+1))/2 where N=n-3 so
sumFirstN = (n-3)(n-2)/2

similarly

sumFirstNSquare = N*(N+1)*(2*N+1)/6 = (n-3)(n-2)(2n-5)/6

Suppose repeated elements are = X and Y

so X + Y = sumA - sumFirstN;
X*X + Y*Y = sumASquare - sumFirstNSquare;

So on solving this quadratic we can get value of X and Y.
Time Complexity = O(n)
space complexity = O(1)

Answer 10

Сортировка массива может показаться лучшим решением. Простая сортировка сделает поиск тривиальным и займет намного меньше времени / пространства.

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

int count [10];

for (int i = 0; i < arraylen; i++) {
    count[array[i]]++;
}

Тогда просто ищите в вашем массиве любые числа больше 1. Это элементы с дубликатами. Требуется только один проход по исходному массиву и один проход по массиву count.