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

Question

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

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

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

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

Answer 1

Почему мы должны пытаться делать математику (специально решая квадратные уравнения), это дорогостоящие операции. Лучший способ решить эту проблему - создать битовую карту размером (n-3) битов, т.е. (n -3) +7 / 8 байтов. Лучше сделать calloc для этой памяти, поэтому каждый бит будет инициализирован в 0. Затем просмотрите список и установите конкретный бит на 1, если он встречается, если бит уже установлен на 1 для этого нет, то это повторное нет. Это может быть расширено, чтобы узнать, есть ли какие-либо пропущенные нет в массиве или нет. Это решение O (n) во временной сложности

Answer 2

for(i=1;i<=n;i++) {
  if(!(arr[i] ^ arr[i+1]))
        printf("Found Repeated number %5d",arr[i]);
}

Answer 3

Для каждого числа: проверьте, существует ли оно в остальной части массива.

Answer 4

Как насчет этого:

for (i=0; i<n-1; i++) {
  for (j=i+1; j<n; j++) {
    if (a[i] == a[j]) {
        printf("%d appears more than once\n",a[i]);
        break;
    }
  }
}

Конечно, он не самый быстрый, но он прост и понятен и требует нет дополнительной памяти. Если n - это небольшое число, например 9 или 100, тогда оно вполне может быть «лучшим». (т. е. «лучший» может означать разные вещи: самый быстрый для выполнения, наименьший объем памяти, самый обслуживаемый, наименьший объем затрат на разработку и т. д.)