Самые часто встречающиеся элементы
Дан целочисленный массив nums и число k. Верните k наиболее часто встречающихся элементов массива. Порядок элементов в возвращаемом массиве не важен.
Пример 1:
Input: nums = [1,2,2,3,3,3], k = 2 Output: [3,2]
Пример 2:
Input: nums = [1], k = 1 Output: [1]
Пример 3:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Рекомендуемая временная и пространственная сложность
Оптимальное решение имеет временную сложность O(n) и пространственную сложность O(n), где n — размер входного массива.
Подсказка 1
Первый шаг - подсчитать частоту каждого элемента. Какую структуру данных лучше использовать для этого?
Подсказка 2
После подсчета частот, как эффективно найти k наиболее часто встречающихся элементов? Подумайте о структурах данных, которые хорошо работают с поиском top-k элементов.
Подсказка 3
Вместо использования сортировки или кучи, подумайте о методе Bucket Sort. Так как частота элемента не может превышать размер массива, мы можем использовать массив "корзин", где индекс - это частота.