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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

Ответ 4

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

- Перемещение по всему массиву. Вы должны это сделать. Нет способа бить O (n).

for each number:
  if it 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).

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

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

Ответ 5

Я думаю, что мы неправильно читаем эту задачу. Он просит "найти единственное целочисленное значение в массиве, которое происходит с четной частотой". Итак, предполагая, что существует ровно один элемент, решение равно:

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
}