Определение элемента, который больше всего проявился в O (n) времени и O (1) пространстве

Ответ 1

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

Как amit указывает на, решая это, мы находим решение элементность проблема (определение того, являются ли все элементы списка различными), что, как было доказано, занимает Θ(n log n) время, когда не используется элемент для индексации памяти компьютера. Если бы мы использовали элементы для индексации памяти компьютера, учитывая неограниченный диапазон значений, для этого требуется не менее Θ(n) пробела. Учитывая сокращение этой проблемы до этой, границы этой проблемы обеспечивают одинаковые границы этой проблемы.

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

2 варианта:

• Сортировка

  Сохранение массива числа вхождений каждого элемента (индекс массива - это элемент), выводящего наиболее частое.

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

  Связанные опции сортировка radix (имеет вариант на месте, похожий на quicksort) и сортировка ведра.

• Quicksort

  Повторное разбиение данных на основе выбранной оси (путем замены) и рекурсии на разделах.

  После сортировки мы можем просто перебирать массив, отслеживая максимальное количество последовательных элементов.

  Это займет время O(n log n) и O(1).

Ответ 2

Как вы говорите, максимальный элемент в вашем кеше может иметь очень большое число, но следующее является одним из решений.

• Итерации по массиву.
• Допустим, что максимальный элемент, который имеет массив, равен m.
• Для каждого индекса я получаю элемент, который он содержит, пусть это будет массив [i]
• Теперь перейдите в индексный массив [i] и добавьте m к нему.
• Сделайте выше для всех индексов в массиве.
• Наконец, итерация по массиву и индекс возврата с максимальным элементом.

TC → O (N) SC → O (1)

Это может быть невыполнимо для больших m, как в вашем случае. Но посмотрите, можете ли вы оптимизировать или изменить этот алгоритм.

Ответ 3

Решение на голове:
Поскольку числа могут быть большими, поэтому я рассматриваю хеширование вместо того, чтобы хранить их непосредственно в массиве.

Пусть есть n чисел 0 до n-1.
Предположим, что число окклюдирует максимальное время, occour K раз.
Создадим ведра n/k, изначально все пустое.

hash(num) указывает, присутствует ли num в любом из ведро. hash_2(num) хранит количество раз num присутствует в любом из ведра.

для (i = 0 до n-1)

• Если число уже присутствует в одном из ведер, увеличьте количество input[i], что-то вроде Hash_2(input[i]) ++
• else найдите пустое ведро, вставьте input[i] в 1 пустое ведро. Hash(input[i]) = true
• else, если все ведра заполнены, уменьшите количество всех чисел в кодах на 1, не добавляйте input[i] в любой из ковшей.
  Если количество любых чисел становится равным нулю (см. Hash_2 (number)], Hash(number) = false.

Таким образом, наконец, вы получите элементы atmost k, а необходимое число - одно из них, поэтому вам нужно снова пройти вход O(N), чтобы наконец найти фактическое число.

Используемое пространство O(K), а временная сложность O(N), учитывая реализацию хеша O(1).
Таким образом, производительность действительно зависит от K. Если k << n, этот метод работает плохо.

Ответ 4

Я не думаю, что это отвечает на вопрос, как указано в названии, но на самом деле вы можете реализовать кэш с политикой выживания с наименее часто используемой политикой, имеющей постоянное среднее время для операций put, get и remove. Если вы правильно поддерживаете структуру данных, нет необходимости проверять все элементы, чтобы найти элемент для выселения.

Идея имеет хеш-таблицу, которая отображает ключи для значений записей. Запись значения содержит само значение плюс ссылку на "счетчик node". Счетчик node является частью дважды связанного списка и состоит из:

• Счетчик доступа
• Набор ключей, имеющих этот счет доступа (как хэш-набор)
• следующий указатель
• prev pointer

Список поддерживается таким образом, что он всегда сортируется с помощью счетчика доступа (где голова min), а значения счетчика уникальны. A node с счетчиком доступа C содержит все ключи, имеющие этот счет доступа. Обратите внимание, что это не увеличивает общую пространственную сложность структуры данных.

Операция get (K) включает в себя продвижение K путем переноса ее на другую запись счетчика (либо новую, либо следующую в списке).

Операция выключения, инициированная операцией put, состоит примерно в проверке заголовка списка, удалении произвольного ключа из его набора ключей и затем его удалении из хеш-таблицы.

Ответ 5

Возможно, если мы сделаем разумные (для меня, во всяком случае) предположения о вашем наборе данных.

Как вы говорите, вы могли бы это сделать, если бы вы могли хешировать, потому что вы можете просто подсчитывать по-хэш. Проблема в том, что вы можете получить не-уникальные хэши. Вы указываете 20-битные числа, поэтому предположительно 2 ^ 20 возможных значений и желание небольшого и фиксированного объема рабочей памяти для фактического хеш-счета. Это, как предполагается, приведет, таким образом, к хеш-коллизиям и, следовательно, к разрушению алгоритма хэширования. Но вы можете исправить это, выполнив более одного прохода с дополнительными алгоритмами хеширования.

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

Предполагая выравнивание слова; это означает, что у нас есть 18 бит хэша.

Затем вы, вероятно, имеете максимальный размер кеша, который, по-видимому, довольно мал. Я собираюсь предположить, что вы выделяете максимум <= 256 элементов, потому что тогда мы можем использовать один байт для счета.

Хорошо, поэтому, чтобы сделать наши хеши, мы разбиваем число в кеше на два девятибитных числа, в порядке значимости от наивысшего до самого низкого и отбрасываем последние два бита, как обсуждалось выше. Возьмите первый из этих кусков и используйте его как хэш, чтобы дать счет первой части. Затем мы берем второй из этих кусков и используем его как хэш, но на этот раз мы только рассчитываем, соответствует ли хэш первой части той, которую мы определили как имеющую самый высокий хеш. Тот, который остается с самым высоким хешем, теперь уникально идентифицирован как имеющий наибольший счет.

Это выполняется в O (n) времени и для подсчета требуется таблица с байтом в 512 байт. Если это слишком большая таблица, вы можете разделить на три куска и использовать таблицу с 64 байтами.

Добавлено позже

Я думал об этом, и я понял, что у него есть условие отказа: если первый проход подсчитывает две группы с одинаковым количеством элементов, он не может эффективно различать их. Ну хорошо

Ответ 6

Предположение: весь элемент является целым числом, для другого типа данных мы также можем достичь этого, если мы используем hashCode()

Мы можем достичь временной сложности O (nlogn), а пространство O (1).

Сначала отсортируйте массив, сложность по времени - O (nlog n) (мы должны использовать локальный алгоритм сортировки, например quick sort, чтобы сохранить сложность пространства)

Используя четыре целые переменные, current, которая указывает значение, на которое мы ссылаемся, count, которое указывает количество вхождений current, result, которое указывает результат финала и resultCount, которые указывают число вхождений result

Итерация от начала до конца массива data

  int result = 0;
  int resultCount = -1;
  int current = data[0];
  int count = 1;

  for(int i = 1; i < data.length; i++){
       if(data[i] == current){
            count++;
      }else{
           if(count > resultCount){
               result = current;
               resultCount = count;
           }
           current = data[i];
           count = 1;
       }
  }
  if(count > resultCount){
      result = current;
      resultCount = count;
  }
  return result;

Итак, в конце используется только 4 переменных.