347. Top K Frequent Elements

leetcode medium

#array#backtracking#csharp#hash-table#heap#leetcode#medium#sort

Task

Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.

Пример

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

C# solution

matched/original

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var count = nums.GroupBy(n => n)
                        .ToDictionary(g => g.Key, g => g.Count());
        return count.OrderByDescending(x => x.Value)
                    .Take(k)
                    .Select(x => x.Key)
                    .ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& TopKFrequent(vector<int>& nums, int k) {
        var count = nums.GroupBy(n => n)
                        .ToDictionary(g => g.Key, g => g.size()());
        return count.OrderByDescending(x => x.Value)
                    .Take(k)
                    .Select(x => x.Key)
                    .ToArray();
    }
}

Java solution

matched/original

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue());
        heap.addAll(count.entrySet());
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(heap.poll().getKey());
        }
        return result;
    }
}

Python solution

matched/original

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        return heapq.nlargest(k, count.keys(), key=count.get)

Explanation

Algorithm

Подсчет частоты:

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

Создание кучи:

Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов.

Возврат результата:

Верните k самых частых элементов.

😎