План курса / Все задачи / Алгоритмы и структуры данных
Топ K частых элементов
сложно
# решено
Дан массив целых чисел nums и число k. Необходимо вернуть k наиболее часто встречающихся элементов. Результат можно вернуть в любом порядке.
Пример 1:
Ввод: nums = [5,7,5,6,6,5], k = 2
Вывод: [5,6]
Объяснение: элемент 5 встречается 3 раза, элемент 6 встречается 2 раза, а элемент 7 всего один, поэтому мы возвращаем 5 и 6, так как они топ 2 самых встречающихся элементов.
Пример 2:
Ввод: nums = [3,4,3], k = 1
Вывод: [3]
Ограничения:
1 <= len(nums)
Число k находится в пределах от 1 до количества уникальных элементов в массиве.
Гарантируется, что ответ уникален.
public class Solution
{
public static List<int> TopKFrequent(List<int> nums, int k)
{
// Ключ - число, значение - сколько раз встретилось
var count = new Dictionary<int, int>();
foreach (var num in nums)
{
if (count.ContainsKey(num))
{
count[num]++;
}
else
{
count[num] = 1;
}
}
// Индекс - частота, значение - список чисел с такой частотой
var frequencyList = new List<List<int>>(new List<int>[nums.Count + 1]);
for (int i = 0; i <= nums.Count; i++)
{
frequencyList[i] = new List<int>();
}
foreach (var entry in count)
{
frequencyList[entry.Value].Add(entry.Key);
}
// Проходим с конца и собираем первые k элементов
var result = new List<int>();
for (int i = frequencyList.Count - 1; i >= 0 && k > 0; --i)
{
foreach (var num in frequencyList[i])
{
if (k <= 0) break;
result.Add(num);
k--;
}
}
return result;
}
}
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> topKFrequent(const vector<int>& nums, int k) {
// ключ - число, значение - сколько раз встретилось
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
// индекс - частота, значение - список чисел с такой частотой
vector<vector<int>> frequencyList(nums.size() + 1);
for (auto& entry : count) {
frequencyList[entry.second].push_back(entry.first);
}
// проходим с конца и собираем первые k элементов
vector<int> result;
for (int i = frequencyList.size() - 1; i >= 0 && k > 0; --i) {
for (int j = 0; j < frequencyList[i].size() && k > 0; j++) {
result.push_back(frequencyList[i][j]);
--k;
}
}
return result;
}
package main
func topKFrequent(nums []int, k int) []int {
// ключ - число, значение - сколько раз встретилось
count := make(map[int]int)
for _, num := range nums {
count[num]++
}
// индекс - частота, значение - список чисел с такой частотой
freqList := make([][]int, len(nums)+1)
for num, freq := range count {
freqList[freq] = append(freqList[freq], num)
}
// проходим с конца и собираем первые k элементов
result := []int{}
for i := len(freqList) - 1; i >= 0 && k > 0; i-- {
for _, num := range freqList[i] {
if k <= 0 {
return result
}
result = append(result, num)
k--
}
}
return result
}
import java.util.*;
public class Solution {
public List<Integer> topKFrequent(List<Integer> nums, int k) {
// ключ - число, значение - сколько раз встретилось
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.merge(num, 1, Integer::sum);
}
// индекс - частота, значение - список чисел с такой частотой
List<List<Integer>> frequencyList = new ArrayList<>();
for (int i = 0; i <= nums.size(); i++) {
frequencyList.add(new ArrayList<>());
}
for (var entry : count.entrySet()) {
frequencyList.get(entry.getValue()).add(entry.getKey());
}
// проходим с конца и собираем первые k элементов
List<Integer> result = new ArrayList<>();
for (int i = frequencyList.size() - 1; i >= 0 && k > 0; i--) {
for (int num : frequencyList.get(i)) {
if (k <= 0) return result;
result.add(num);
k--;
}
}
return result;
}
}
import java.util.*;
public class Solution {
public List<Integer> topKFrequent(List<Integer> nums, int k) {
// ключ - число, значение - сколько раз встретилось
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.merge(num, 1, Integer::sum);
}
// индекс - частота, значение - список чисел с такой частотой
List<List<Integer>> frequencyList = new ArrayList<>();
for (int i = 0; i <= nums.size(); i++) {
frequencyList.add(new ArrayList<>());
}
for (var entry : count.entrySet()) {
frequencyList.get(entry.getValue()).add(entry.getKey());
}
// проходим с конца и собираем первые k элементов
List<Integer> result = new ArrayList<>();
for (int i = frequencyList.size() - 1; i >= 0 && k > 0; i--) {
for (int num : frequencyList.get(i)) {
if (k <= 0) return result;
result.add(num);
k--;
}
}
return result;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @returns {number[]}
*/
export function topKFrequent(nums, k) {
// ключ - число, значение - сколько раз встретилось
const count = new Map();
for (const num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
// индекс - частота, значение - список чисел с такой частотой
const frequencyList = new Array(nums.length + 1).fill().map(() => []);
for (const [num, freq] of count.entries()) {
frequencyList[freq].push(num);
}
// проходим с конца и собираем первые k элементов
const result = [];
for (let i = frequencyList.length - 1; i >= 0 && k > 0; i--) {
for (const num of frequencyList[i]) {
if (k <= 0) return result;
result.push(num);
k--;
}
}
return result;
}