Какой самый быстрый алгоритм, чтобы найти элемент с самой высокой частотой в массиве

Question

У меня есть два входных массивов X и Y. Я хочу вернуть этот элемент массива X, который происходит с высокой частотой в массиве Y.

наивный способ выполнения этого требует, чтобы для каждого элемента x массива X я линейно искал массив Y для его числа вхождений и затем возвращал тот элемент x, который имеет самую высокую частоту. Вот алгоритм псевдо:

max_frequency = 0 
max_x = -1    // -1 indicates no element found 
For each x in X 
    frequency = 0 
    For each y in Y 
     if y == x 
      frequency++ 
    End For 
    If frequency > max_frequency 
     max_frequency = frequency 
     max_x = x 
    End If 
End For 
return max_x 

Как есть два вложенных циклов, временная сложность для этого алгоритма будет O (N^2). Могу ли я сделать это в O (nlogn) или быстрее?

Answer 1

используйте хэш-таблицу ключей сопоставления с подсчетами. Для каждого элемента массива сделайте, например, counts[element] = counts[element] + 1 или эквивалент вашего языка.

В конце проведите через отображения в хэш-таблице и найдите макс.

Answer 2

Может сделать quicksort, а затем пересечь его с переменной, которая подсчитывает, сколько из числа находится в строке +, что это за номер. Это должно дать вам NlogN

Answer 3

Merge Сортировку основе Разделяй и властвуй Концепция дает O (NlogN) сложность

Answer 4

В качестве альтернативы, если у вас могут быть дополнительные структуры данных, вы ходите по массиву Y, для каждого номера, обновляющего его частоту в хеш-таблице. Это занимает O(N(Y) раз. Затем пройдите X, найдя, какой элемент в X имеет самую высокую частоту. Это занимает O(N(X)) раз. В целом: линейное время, и поскольку вы должны смотреть на каждый элемент как X, так и Y в любой реализации хотя бы один раз (EDIT: Это не совсем верно для всех случаев/всех реализаций, так как jwpat7 указывает, хотя это правда в худшем случае), вы не можете сделать это быстрее, чем это.

Answer 5

Временная сложность общих алгоритмов перечислены ниже:

Algorithm  | Best | Worst | Average 
--------------+-----------+-----------+---------- 
MergeSort  | O(n lg n) | O(n lg n) | O(n lg n) 
InsertionSort | O(n) | O(n^2) | O(n^2) 
QuickSort  | O(n lg n) | O(n^2) | O(n lg n) 
HeapSort  | O(n lg n) | O(n lg n) | O(n lg n) 
BinarySearch | O(1) | O(lg n) | O(lg n) 

В целом, при прохождении по списку, чтобы выполнить определенные критерии, вы действительно не можете сделать лучше, чем линейное время. Если вам нужно сортировать массив, я бы сказал, что придерживайтесь Mergesort (очень надежным), чтобы найти элемент с наивысшей частотой в массиве.

Примечание: Предполагается, что вы хотите использовать алгоритм сортировки. В противном случае, если вам разрешено использовать любую структуру данных, я бы пошел с структурой типа hashmap/hashtable с постоянным временем поиска. Таким образом, вы просто сопоставляете ключи и обновляете пару ключевых значений частоты. Надеюсь это поможет.

Answer 6

Ваш предложенный подход будет O (n^2), если оба списка имеют длину n. Скорее всего, списки могут быть разной длины, поэтому временная сложность может быть выражена как O (mn).

Вы можете разделить вашу проблему в два этапа: 1. Заказ уникальных элементов из Y по частоте 2. Найдите первый элемент из этого списка, который существует в X

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

Answer 7

1-й шаг: Сортировка X и Y. Предполагая, что их соответствующие длины: m и n, сложность этого этапа будет O(n log n) + O(m log m).

2-й шаг: рассчитывать каждый Х _я в Y и отслеживать максимальное количество до сих пор. Поиск X _я в отсортированный Y является O(log n). Общая сложность второго шага:

Общая сложность: O(n log n) + O(m log m) + O(m log n) или Simpified: O(max(n,m) log n)

Answer 8

Сортировка X и Y. Тогда же сортировка слияние. Подсчитайте частоты от Y каждый раз, когда он встречается с одним и тем же элементом в X.

Так сложность, O (nlogn) + O (mlogm) + O (m + n) = O (klogk) где n, m = длина X, Y; k = max (m, n)