Учитывая массив целых чисел, где некоторые числа повторяются 1 раз или 2 раза, но одно число повторяется 3 раза, как вы находите это?

Question

Учитывая массив целых чисел, где некоторые числа повторяются 1 раз, некоторые числа повторяются 2 раза, и только одно число повторяется 3 раза, как найти число, которое повторяется 3 раза.Использование хэша было запрещено.Сложность алгоритма должна быть O (n)

Answer 1

int count[2^32];
for x in input:
  count[x] = 0;  // delete this loop if you can assume ram is cleared to 0.
for x in input:
  count[x]++;
for x in input:
  if count[x] == 3:
    return x

Пожалуйста, извините за сочетание языков :-) Кроме того, очень глупо иметь массив, который можно индексировать любым целым числом - вы можете сделать это в 64-битной системе, и она соответствует требованиям.

Answer 2

Если вы знаете min и max последовательности целых чисел и min> = 0, создайте массив [min, max], заполненный нулями. Просканируйте данный массив и, если это произойдет, увеличьте i-ую позицию на единицу. После окончания у вас есть таблица частот во втором массиве, где позиция массива указывает на целое число.