Найти единственное целое число, которое встречается с четной частотой в данном массиве целых чисел, когда все остальные встречаются нечетно с частотой

Question

Это вопрос интервью.

Учитывая массив целых чисел, найдите одно целое значение в массиве, которое встречается с четной частотой. Все целые числа будут положительными. Все остальные числа встречаются нечетной частоты. Максимальное число в массиве может быть INT_MAX.

Например, [2, 8, 6, 2] должно вернуть 2.

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

Я знаю, как решить эту проблему с помощью хеш-таблицы (traverse и count freq). Это O (n) время и пространство.

Можно ли решить это за O (1) пробел или лучшее время?

Answer 1

Учитывая, что это вопрос интервью, ответ таков: O (1) пробел достижим "для очень больших значений 1":

• Подготовить спичечный массив 1..INT_MAX из всех 0
• При обходе массива используйте целое число в качестве индекса в массиве совпадений, добавляя 1
• Когда закончите, просмотрите массив совпадений, чтобы найти одну запись с положительным четным значением

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

Answer 2

Если вам разрешено сортировать исходный массив, я считаю, что вы можете сделать это за время O (n lg U) и пространство O (lg U), где U - максимальный элемент массива.Идея заключается в следующем: используя радикальную сортировку MSD на месте , отсортируйте массив по времени O (n lg U) и O (lg U).Затем выполните итерацию по всему массиву.Поскольку все равные значения являются последовательными, вы можете подсчитать, сколько раз появляется каждое значение.Как только вы найдете значение, которое появляется четное количество раз, вы можете вывести ответ.Для этого второго сканирования требуется время O (n) и пространство O (1).

Если мы предположим, что U является фиксированной константой, это дает алгоритм O (n) -времени O (1) -пространства.Если вы этого не предполагаете, то использование памяти все еще лучше, чем алгоритм O (n), при условии, что lg U = O (n), что должно быть верно на большинстве машин.Кроме того, использование пространства только логарифмически столь же велико как самый большой элемент, означая, что практическое использование пространства довольно хорошо.Например, на 64-битной машине нам понадобится только место, достаточное для хранения 64 рекурсивных вызовов.Это намного лучше, чем выделять гигантский массив заранее.Более того, это означает, что алгоритм является алгоритмом со слабым полиномиальным временем как функция от U.

Тем не менее, это переставляет исходный массив и, таким образом, деструктивно модифицирует входные данные.В некотором смысле, это обман, потому что он использует сам массив для хранения O (n).

Надеюсь, это поможет!

Answer 3

Просматривать список, сохраняя два набора: набор «Четный» и набор «Нечетный».Если элемент ранее не был виден (т. Е. Если он ни в одном из наборов), поместите его в набор «Нечетные».Если элемент находится в одном наборе, переместите его в другой набор.В конце в наборе «Четный» должен быть только один предмет.Это, вероятно, не будет быстрым, но использование памяти должно быть разумным для больших списков.

Answer 4

Полагаю, мы неправильно прочитали задание. Он просит нас «найти единственное целочисленное значение в массиве, которое встречается с четной частотой». Итак, если предположить, что существует ровно ОДИН четный элемент, решение будет следующим:

public static void main(String[] args) {
    int[] array = { 2, 1, 2, 4, 4 };

    int count = 0;
    for (int i : array) {
        count^=i;
    }
    System.out.println(count); // Prints 1
}

Answer 5

-Создать хеш-таблицу, содержащую целые. Назовите это is_odd или что-то. Поскольку вам, возможно, придется просматривать массив размером INT_MAX, просто сделайте его массивом размера INT_MAX. Инициализировать до 0.

-Пройти через весь массив. Вы должны сделать это. Там нет никакого способа победить O (n).

for each number:
  if it's not in the hash table, mark its spot in the table as 1.

  if it is in the hash table then:
    if its value is '1', make it '2'
    if its value is '2', make it '1'.

Теперь вам нужно пройти через хеш-таблицу. Вытащите единственную запись с «2» в качестве значения.

Время: Вы пересекаете массив один раз и хеш-таблицу один раз, поэтому O (n).

Space: Просто массив размером INT_MAX. Или, если вы знаете диапазон вашего массива, вы можете ограничить использование вашей памяти этим.

edit: Я только что видел, что у вас уже был этот метод. Извините за это!