azl397985856 commented 2 years ago

347. 前 K 个高频元素

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/top-k-frequent-elements/

前置知识

哈希表
堆排序

快速选择

题目描述


给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:

输入: nums = [1], k = 1 输出: [1]

提示：

1 <= nums.length <= 10^5 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

zjsuper commented 2 years ago

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: if k == 0: return [] if k > len(nums): return nums dic = {} for i in nums: if i not in dic: dic[i] = 1 else: dic[i] += 1

    dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
    ans = []
    for i in range(k):
        ans.append(dic[i][0])

    return ans

rzhao010 commented 2 years ago

Thoughts Use HashMap to count the. frequency each number shows Use heap to record the top k

Code


class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[k];
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (Integer key: map.keySet()) {
            if (heap.size() < k) {
                heap.add(key);
            } else if (map.get(key) > map.get(heap.peek())){
                heap.remove();
                heap.offer(key);
            }
        }
        int idx = k - 1;
        while (!heap.isEmpty()) {
            res[idx--] = heap.remove();
        }
        return res;
    }
}

Complexity Time: O(nlogn) Space: O(n)

maybetoffee commented 2 years ago

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        //int[]{num, freq}
        //建一个小顶堆，堆顶最小，freq越大越优先
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
           public int compare(int[] m, int[] n){
               return m[1] - n[1];
           } 
        });

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int num = entry.getKey(), freq = entry.getValue();
            if(pq.size() == k){
                if(pq.peek()[1] < freq){
                    pq.poll();
                    pq.offer(new int[]{num, freq});
                }
            }else{
                pq.offer(new int[]{num, freq});
            }
        }

        int[] res = new int[k];
        for(int i = 0; i < k; i++){
            res[i] = pq.poll()[0];
        }
        return res;
    }
}

forestie9 commented 2 years ago

Ideas

HashMap, heap

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        c = collections.Counter(nums)
        h = []
        for key, val in c.items():
            if len(h) < k:
                heapq.heappush(h, [val, key])
            else:
                heapq.heappushpop(h, [val, key])            
        return [key for val, key in h]

Complexity

Time O(nlogk), space O(n)

shawnhu23 commented 2 years ago

Idea

Use a map to store all elements as key and their number of occurrence as value, and then use a PriorityQueue to sort them by frequency.

Code

class Solution {
    static class Num {
        int number;
        int frequent;

        public Num(int n, int f) {
            this.number = n;
            this.frequent = f;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                int freq = map.get(nums[i]);
                map.put(nums[i], freq+1);
            }
            else {
                map.put(nums[i], 1);
            }
        }
        PriorityQueue<Num> q = new PriorityQueue<>((n1, n2) -> n2.frequent - n1.frequent);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            q.add(new Num(entry.getKey(), entry.getValue()));
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = q.poll().number;
        }
        return res;
    }
}

Complexity

Time: O(nlogn) Space: O(n)

zqwwei commented 2 years ago

Code

看到更好的解法了，但还是把我本来的做法贴出来吧

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        numFreqMap = collections.defaultdict(int)
        for num in nums:
            numFreqMap[num] += 1

        numFreqMap = sorted(numFreqMap.items(), key=lambda x: -x[1])
        return [pair[0] for pair in numFreqMap][:k]

Complexity

O(n log n) not optimal
O(n)

antmUp commented 2 years ago

思路

1、先生成一个hash表； 2、通过遍历的方式将出现的次数维护到hash表中； 3、最后将符合条件的key塞到新数组中返回

代码


// hash表的方式
function topKFrequent(nums, k) {
  // 生成一个hash结构
  let hash = new Map();

  // 遍历维护一组hash数据
  for (let i = 0; i < nums.length; i++) {
    if (hash.has(nums[i])) {
      let value = hash.get(nums[i]);

      hash.set(nums[i], value+1);
    } else {
      hash.set(nums[i], 1);
    }
  }

  // 将符合条件的值维护到数组中返回
  let res = [];
  for (let [ key, values ] of hash) {
      console.log(key, values);
    if (values >= k) {
      res.push(key);
    }
  }

  return res;
}

复杂度分析

时间复杂度：O(N);
空间复杂度：O(N) ,N为数组的长度

lizimu0709 commented 2 years ago

思路

把记录的数字和对应的出现次数放到堆中
如果堆已满且当前数的次数比堆顶大，用当前元素替换堆顶元素

返回

class Solution {
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for(int num : nums){
        count.put(num, count.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
        public int compare(int[] m, int[] n){
            return m[1] - n[1];
        }
    });

    for(Map.Entry<Integer, Integer> entry : count.entrySet()){
        int num = entry.getKey(), cnt = entry.getValue();
        if(queue.size() == k){
            if(cnt > queue.peek()[1]){
                queue.poll();
                queue.offer(new int[]{num, cnt});
            }
        }else{
            queue.offer(new int[]{num, cnt});
        }
    }

    int[] res = new int[k];
    for(int i = 0; i < k; i++){
        res[i] = queue.poll()[0];
    }
    return res;
}
}

时间复杂度：O(nlogk)
空间复杂度：O(n)

houmk1212 commented 2 years ago

思路

使用哈希表记录每个元素出现的次数。 topK问题可以使用堆，固定堆的大小为k,遍历哈希表，如果堆已经填满，需要和堆顶元素比较。

代码

class Solution {
   public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int[] res = new int[k];
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        for (Integer key : map.keySet()) {
            int[] tmp = new int[2];
            tmp[0] = key;
            tmp[1] = map.get(key);

            if (q.size() >= k && q.peek()[1] < tmp[1]) {
                q.remove();
                q.offer(tmp);
            } else if (q.size() < k) {
                q.offer(tmp);
            }
        }

        for (int i = 0; i < res.length; i++) {
            res[i] = q.remove()[0];
        }

        return res;
    }
}

复杂度

时间复杂度： O(NlogK)
空间复杂度： O(N)

ZacheryCao commented 2 years ago

Idea

Heap + Hashmap

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        heap = []
        freq = collections.Counter(nums)
        for f in freq:
            if len(heap) < k:
                heapq.heappush(heap, (freq[f], f))
            else:
                if freq[f] > heap[0][0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, (freq[f], f))
        return [h[1] for h in heap]

Complexity:

Time: O(N log K) Space: O(N)

hyh331 commented 2 years ago

Day20 思路

借助哈希表来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
    //1.map记录元素出现的次数
        unordered_map<int,int>map;//两个int分别是元素和出现的次数
        for(auto& c:nums){
            map[c]++;
        }
    //2.利用优先队列，将出现次数排序
        //自定义优先队列的比较方式，小顶堆
        struct myComparison{
            bool operator()(pair<int,int>&p1,pair<int,int>&p2){
                return p1.second>p2.second;//小顶堆是大于号
            }
        };
        //创建优先队列,pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison> q;
        //遍历map中的元素
        //1.管他是啥，先入队列，队列会自己排序将他放在合适的位置
        //2.若队列元素个数超过k，则将栈顶元素出栈（栈顶元素一定是最小的那个）
        for(auto& a:map){
            q.push(a);
            if(q.size()>k){
               q.pop(); 
            }
        }
        //将结果导出
        vector<int>res;
        while(!q.empty()){
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;

    }
};

复杂度分析

时间复杂度：O(Nlogk)
空间复杂度：O(N)

duke-github commented 2 years ago

思路

优先队列 将数组中的全部数出现的次数做次数统计并放入hash表 循环hash表 将值，出现的次数放入以次数为比较对象的有点队列中，
如果队列已满 判断下一元素的出现次数是否大于队列中最小的出现次数 大于则替换

复杂度

时间复杂度O(n log n) 空间复杂度O(n)

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //Comparator.comparingInt(o -> o[1]) 返回一个比较器 该比较器以int排序lambda表达式中是如何获取这个用于比较的int
        //PriorityQueue 优先队列 以构造器中的比较器参数为排序规则排序
        PriorityQueue<int[]> queue = new PriorityQueue<>((Comparator.comparingInt(o -> o[1])));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() == k) {
                final int[] peek = queue.peek();
                if (peek[1] < entry.getValue()) {
                    queue.poll();
                    queue.offer(new int[]{entry.getKey(), entry.getValue()});
                }
            } else {
                queue.offer(new int[]{entry.getKey(), entry.getValue()});
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; ++i) {
            ans[i] = queue.poll()[0];
        }
        return ans;
    }

}

KelvinG-LGTM commented 2 years ago

思路

heap: 时刻保证heap里面有k个数.

小细节: heapq.heappush(heap, (occ, num)) 自动会根据occ大小排序. 同时pop的时候也会将当前occ最小的tuple弹出.

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        heap = []

        for num, occ in freq.items(): 
            if len(heap) < k: 
                heapq.heappush(heap, (occ, num))
            else: 
                heapq.heappush(heap, (occ, num))
                heapq.heappop(heap)

        res = []
        for i in heap: 
            res.append(i[1])
        return res

复杂度分析

时间复杂度

O(log(N))

空间复杂度

O(N)

反思

如何联系到生产环境?

KelvinG-LGTM commented 2 years ago

思路 2 - 快速排序

快排: 一般看到求前K个排序的什么东西, 都可以联想到Quick sort.

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        num_cnt = list(count.items())
        topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1)
        return [item[0] for item in topKs]

    def findTopK(self, num_cnt, k, low, high):
        pivot = random.randint(low, high)
        num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]
        base = num_cnt[low][1]
        i = low
        for j in range(low + 1, high + 1):
            if num_cnt[j][1] > base:
                num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]
                i += 1
        num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
        if i == k - 1:
            return num_cnt[:k]
        elif i > k - 1:
            return self.findTopK(num_cnt, k, low, i - 1)
        else:
            return self.findTopK(num_cnt, k, i + 1, high)

复杂度分析

时间复杂度

O(NlogN)

空间复杂度

O(logN)

Magua-hub commented 2 years ago


class Solution {
public:

    vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for(auto x : nums) cnt[x] ++;//统计每个元素的出现次数
    int n = nums.size();
    vector<int> s(n + 1);//记录出现每种次数的元素个数是多少
    for(auto[x, c] : cnt) s[c] ++;//元素x出现c次，所以在c处++,s数组的下标是出现的次数
    int i = n, t = 0;//找分界点，t记录的是从大到小元素出现次数的累加
    while(t < k) t += s[i --];//while。这一步的目的主要是确定分界点，循环结束后，分界点是i和i + 1，i代表的是出现次数
    vector<int> res;
    for(auto[x, c] : cnt)//循环哈希表，如果出现次数大于i，即说明出现次数是前k个的
        if(c > i)//i是分界点
            res.push_back(x);

    return res;
    }
};

oneline-wsq commented 2 years ago

思路

首先记录每个数字的出现次数，再排序，得到前k个元素

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 首先对数组排序
        nums.sort()
        pre=nums[0]
        n=0
        cn=dict()
        for i in nums:
            if i==pre:
                n+=1
            else:
                cn[pre]=n
                n=1
            cn[i]=n
            pre=i
        # 对字典按照value排序

        cn2=dict(sorted(cn.items(),key=lambda kv:(kv[1],kv[0]),reverse=True))

        i=0
        r=[]
        for key in cn2.keys():
            i+=1
            if i<=k:
                r.append(key)
            else:
                break
        return r

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

okbug commented 2 years ago

思路

使用哈希表存储每个数字出现的次数，然后排序。

代码

var topKFrequent = function(nums, k) {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], -~map.get(nums[i]));
    }

    return Array.from(map).sort((a, b) => b[1] - a[1]).map(i => i[0]).slice(0, k);
};

BlueRui commented 2 years ago

Problem 347. Top K Frequent Elements

Algorithm

Iterate over the array and use a map to keep track of counts of each value.
Use a priority queue to maintain k map entries with the highest frequency.

Complexity

Time Complexity: Creating map takes O(N) time. Iterating entries to create priority queue takes O(Nlogk) time. Total is O(Nlogk).
Space Complexity: O(N).

Code

Language: Java

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> counter = new HashMap<>();
    PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            Map.Entry.<Integer, Integer>comparingByValue());

    for (int num : nums) {
        counter.putIfAbsent(num, 0);
        counter.put(num, counter.get(num) + 1);
    }
    for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = pq.poll().getKey();
    }
    return result;
}

EggEggLiu commented 2 years ago

思路

遍历输入并使用hashMap存入数字元素和其出现次数
把hashMap导入数组中按频次降序排列。

按照题目要求打包输出

代码

var topKFrequent = function(nums, k) {
let res = [];
let hashMap = new Map();
for (let num of nums) {
    if (hashMap.has(num)) {
        hashMap.set(num, hashMap.get(num) + 1);
    } else {
        hashMap.set(num, 1);
    }
}
let arr = Array.from(hashMap);
arr.sort((a, b) => b[1] - a[1]);
for (let i = 0; i < k; i++) {
    res.push(arr[i][0]);
}
return res;
};

dzwhh commented 2 years ago

【Day 20】347.Top K Frequent Elements「前 K 个高频元素」

题目地址: https://leetcode-cn.com/problems/top-k-frequent-elements/

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例 1

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

前置知识

哈希表

思路

先遍历元素把元素和其个数放入哈希表，然后再对哈系表中的value进行排序，最后把前K个元素存入结果输出

代码

js 版本

const topKFrequent = (nums, k) => {
  let map = new Map();

  for(let itm of nums){
    map.set(itm,(map.get(itm) || 0) + 1);
  }

  const arr = [...map].sort((a,b) => b[1] - a[1]);
  const res = [];

  for(let i = 0; i < k; i++){
    res.push(arr[i][0])
  }

  return res;

}

复杂度分析

时间复杂度:O(nlogn) 空间复杂度:O(n)

xixiao51 commented 2 years ago

Idea

Min Heap: use min heap to record the most freq k numbers
Bucket Sort: Build a array of list to be buckets with length + 1 and use freq as index to put each key into buckets. And get first k elements from the end of array.

Code

Min Heap

class Solution {
public int[] topKFrequent(int[] nums, int k) {
    if(k == nums.length) {
        return nums;
    }

    //build hash map: O(N)
    Map<Integer, Integer> map = new HashMap<>();
    for(int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // keep k top frequent elements in the heap
    // O(N log k) = O(klogk) + O((N - k)logk)
    //The time complexity of heap push/pop is O(logk)
    Queue<Integer> heap = new PriorityQueue<>((n1, n2) -> map.get(n1) - map.get(n2));
    for(int key : map.keySet()) {
        heap.offer(key);
        if(heap.size() > k) {
            heap.poll();
        }
    }

    int[] result = new int[k];
    //O(klogk)
    for(int i = k - 1; i >= 0; i--) {
        result[i] = heap.poll();
    }

    return result;
}
}

Bucket Sort

class Solution {
public int[] topKFrequent(int[] nums, int k) {
    if(k == nums.length) {
        return nums;
    }

    //Map the freq into a hashtable
    //O(N)
    Map<Integer, Integer> map = new HashMap<>();
    for(int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    //Use freq as the index of bucket
    //O(N)
    List<Integer>[] bucket = new List[nums.length + 1];
    for(int key : map.keySet()) {
        int freq = map.get(key);
        if(bucket[freq] == null) {
            bucket[freq] = new ArrayList<Integer>();
        }
        bucket[freq].add(key);
    }

    //Start from the most freq and add all the key in each bucket until total reachs k
    //worst O(N)
    List<Integer> res = new ArrayList<>();
    for(int i = nums.length, j = 0; j < k && i > 0; i--) {
        if(bucket[i] != null) {
            res.addAll(bucket[i]);
            j += bucket[i].size();
        }
    }

    return res.stream().mapToInt(Integer::intValue).toArray();
}
}

Complexity Analysis

Time complexity: Heap - O(NlogK); Bucket - O(N)
Space complexity: Heap - O(N); Bucket - O(N)

1973719588 commented 2 years ago

运用哈希表，记录频次

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        for x in nums:
            if x not in dic:
                dic[x] = 1
            else:
                dic[x] += 1

        val = dic.values()
        val = list(val)

        val.sort()
        kmax = val[-k:]

        ls = []
        for z in dic:
            if dic[z] in kmax:
                ls.append(z)

        return ls

时间复杂度：O(NlogN) 空间复杂度：O(N)

L-SUI commented 2 years ago

····js

/**

@param {number[]} nums
@param {number} k
@return {number[]} / var topKFrequent = function(nums, k) { let map = {} for (let i = 0; i < nums.length;i++) { if(map[nums[i]]) { map[nums[i]]++ }else { map[nums[i]] = 1; } } let arr = [] let keys = Object.keys(map) for (let i = 0; i < keys.length;i++) { arr.push({ key: keys[i], value: map[keys[i]] }) } arr.sort((a,b) =>b.value-a.value) console.log(arr) return arr.map((item,index)=>{ if(index<k) { return 1item.key } }).slice(0,k) };

carterrr commented 2 years ago

class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> frequencyMap = new HashMap<>(); for(int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> -a[1])); for(Map.Entry<Integer, Integer> e : frequencyMap.entrySet()) { q.offer(new int[]{e.getKey(), e.getValue()}); } int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = q.poll()[0]; } return res; } }

Jessie725 commented 2 years ago

Idea

Use Map record the freq of each element Use PriorityQueue (min heap) to keep top k frequent elements

Code

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int n : map.keySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(n);
            }
            else {
                if (map.get(n) > map.get(minHeap.peek())){
                    minHeap.poll();
                    minHeap.offer(n);
                }
            }
        }

        int[] res = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            res[i] = minHeap.poll();
            i++;
        }
        return res;
    }
}

Complexity

Time: O(nlogk) size of priorityQueqe is k, n times heapify Space: O(n) size of map

ShawYuan97 commented 2 years ago

代码

语言支持：Python3

Python3 Code:


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        返回前k个频率最高的元素
        """
        # 方法一 调用Counter
        from collections import Counter 
        num_counter = Counter(nums)
        return [ele for ele,_ in num_counter.most_common(k)]

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

代码

语言支持：Python3

Python3 Code:


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        返回前k个频率最高的元素
        """
        # 方法二 使用哈希表
        hashmap = dict()
        for num in nums:
            if num in hashmap:
                hashmap[num] += 1
            else:
                hashmap[num] = 1
        sort_map = sorted(hashmap.items(),key=lambda x:(-x[1],x[0]))
        return [key for key,_ in sort_map][:k]

复杂度分析

令 n 为数组长度。

时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$

MichaelXi3 commented 2 years ago

Idea

使用HashMap将number和frequency绑定
通过PriorityQueue历变出frequency最高的#k_pairs

返回result_array

Code

class Solution {
public int[] topKFrequent(int[] nums, int k) {
    // Create Map to store values and frequency
    Map <Integer, Integer> valFrequency = new HashMap<Integer, Integer>();
    // Create keys and store values
    for (int num: nums) {
        valFrequency.put(num, valFrequency.getOrDefault(num, 0) + 1); // Store the frequency
    }

    // Use PriorityQueue to allocate highest K-frequency
    // int[0] is the keyVal, int[1] is the frequencyVal
    PriorityQueue<int[]> rank = new PriorityQueue<int[]>(new Comparator<int[]>(){
        public int compare(int[] first, int[] second) {
            return first[1] - second[1]; // Compare the frequency, high freq at the end
        }
    });

    // Compare every key&Val entry in HashMap, keep the top Kth element in Queue
    for (Map.Entry<Integer, Integer> entry : valFrequency.entrySet()) {
        int number = entry.getKey();
        int frequency = entry.getValue();

        if (rank.size() == k) {
            if (rank.peek()[1] < frequency) {
                rank.poll();
                rank.offer(new int[] {number, frequency}); // Replace with pair that has higher freq
            }
        } else {
            rank.offer(new int[] {number, frequency});
        }
    }

    // Now we have top Kth freq items in queue, we want to return it
    int[] result = new int[k];
    for (int i=0; i<result.length; i++) {
        result[i] = rank.poll()[0];
    } 
    return result;
}
}

Time & Space Complexity

Time Complexity: O(N*logK)
Space Complexity: O(N)

flaming-cl commented 2 years ago

347. top-k-frequent-elements

Solution

Hash + Sort

Complexity

Time: O(nlogn) for sort()

Space: O(N)

Code

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const hash = {};
for (n of nums) {
if (!hash[n]) hash[n] = 0;
hash[n] += 1;
}
const hashArr = Object.keys(hash);
if (hashArr.length === k) return hashArr; // for nums like [1,1,1,1,1,2,2,2,2] 2, no need to sort for inputs like this
return hashArr.sort((a, b) => hash[b] - hash[a]).filter((n, i) => i + 1 < k);
}

MoonLee001 commented 2 years ago

思路

由于时间复杂度限制，使用hashmap加堆排序的方式

代码

class MinHeap{
  constructor() {
    this.data = [];
  }

  peek() {
    return this.data[0];
  }

  poll() {
    //   const first = this.data.shift();
    //   this.bubbleDown(0);
    //   return first;
    const first = this.data[0];
    const last =  this.data.pop();
    this.data[0] = last;
    this.bubbleDown(0);

    return first;
  }

  offer(val) {
    this.data.push(val);
    this.bubbleUp(this.data.length - 1);
  }

  bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.data[parent][1] > this.data[i][1]) {
        this.swap(parent, i);
        i = parent;
      } else {
          break;
      }
    }
  }

  bubbleDown(i) {
    while(true) {
      let left = i * 2 + 1;
      let right = i * 2 + 2;
      let min = i;
      if (left < this.size() && this.data[min][1] > this.data[left][1]) {
        min = left;
      }

      if (right < this.size() && this.data[min][1] > this.data[right][1]) {
        min = right;
      }

      if (min !== i) {
        this.swap(i, min);
        i = min;
      } else {
        break;
      }
    }
  }

  size() {
    return this.data.length;
  }

  swap(i, j) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }
}
var topKFrequent = function(nums, k) {
  const n = nums.length;
  const map = new Map();
  for (let i = 0; i < n; i++) {
    map.set(nums[i], (map.get(nums[i]) || 0) + 1); 
  }
  const heap = new MinHeap();
  for (let [key, value] of map.entries()) {
        heap.offer([key, value]);
        if (heap.size() > k) {
            heap.poll();
        }
  }
  console.log(heap);
  let res = [];
  let i = 0;
  while (i < k) {
    res.push(heap.data[i][0]);
    i++;
  }
  return res;
}

复杂度分析

时间复杂度：O(nlogk)
空间复杂度：O(n)

TimmmYang commented 2 years ago

思路

暴力法，使用字典统计nums的元素个数，然后按照频次排序。最后取出前k个高频元素并返回。s s

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        for num in nums:
            if num not in dic:
                dic[num] = 1
            else:
                dic[num] += 1
        dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
        res = []
        for key, value in dic:
            res.append(key)
            k -= 1
            if k == 0:
                break
        return res

复杂度

时间复杂度：O(nlogn), n为nums长度

空间复杂度：O(n)

YuyingLiu2021 commented 2 years ago

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return nums

        res = {}
        for num in nums:
            if num not in res:
                res[num] = 0
            else:
                res[num] += 1
        res = sorted(res.items(), key=lambda item:item[1], reverse=True)

        coun = 0
        ans = []
        while coun < k:
            ans.append(res[coun][0])
            coun += 1

        return ans

solution2  暴力 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res=[]
        couter=collections.Counter(nums)
        for i in range(k):
            a=max(couter.keys(),key=couter.get)
            res+=[a]
            del couter[a]
        return res

LyuliangLiu commented 2 years ago

Idea

用PriorityQueue，排序基于map里的freq从小到大，每当size>k时把最小的poll。先遍历nums全加到map里，再遍历map往pq里加。

Code

class Solution {
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    PriorityQueue<Integer> pq = new PriorityQueue<>((n1, n2) -> 
                                                  map.get(n1) - map.get(n2));
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    map.forEach((num, freq) -> {
        pq.offer(num);
        if (pq.size() > k) {
            pq.poll();
        }
    });

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = pq.poll();
    }
    return result;
}
}

Complexity

Time: nlogk
Space: n+k
用空间换时间：bucket[nums.length+1]. 每个slot代表一个freq。每个slot是一个list of 这个freq的nums。time: n; space: n+n.

wenliangchen commented 2 years ago

Idea

Use a map to store all elements as a key and their number of occurrences as values, and then use a PriorityQueue to sort them by frequency.

Code

    public int[] topKFrequent(int[] nums, int k) {
        // O(1) time
        if (k == nums.length) {
            return nums;
        }

        // 1. build hash map : character and how often it appears
        // O(N) time
        Map<Integer, Integer> count = new HashMap();
        for (int n: nums) {
          count.put(n, count.getOrDefault(n, 0) + 1);
        }

        // init heap 'the less frequent element first'
        Queue<Integer> heap = new PriorityQueue<>(
            (n1, n2) -> count.get(n1) - count.get(n2));

        // 2. keep k top frequent elements in the heap
        // O(N log k) < O(N log N) time
        for (int n: count.keySet()) {
          heap.add(n);
          if (heap.size() > k) heap.poll();    
        }

        // 3. build an output array
        // O(k log k) time
        int[] top = new int[k];
        for(int i = k - 1; i >= 0; --i) {
            top[i] = heap.poll();
        }
        return top;
    }

Complexity

O(NlogN)

huiminren commented 2 years ago

题目

LC347 前K个高频元素

思路

自动：python counter，order by nums，取前k个
手动：遍历，用dict手动计数；按照计数排序，取前k个，排序不可取，因为时间复杂度是O(nlogn)
设置一个大小为k的堆，放进k个最大值

代码

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        dict_counter = {}
        for num in nums:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

        # dict_counter = {k: v for k, v in sorted(dict_counter.items(), key=lambda item: item[1], reverse=True)} # leetcode让函数失效了
        # return dict_counter.keys()[:k]

        heap = []
        for key, val in dict_counter.items():
            if len(heap) >= k:
                if val > heap[0][0]:
                    heapq.heapreplace(heap, (val, key))
            else:
                heapq.heappush(heap, (val, key))
        return [item[1] for item in heap]

复杂度

时间复杂度 O(nlogk)
空间复杂度 O(n)

CarrieyqZhang commented 2 years ago

public int[] topKFrequent(int[] nums, int k) {
        //特判
        if(nums==null||nums.length==0){
            return null;
        }
        Map<Integer,Integer> map =new HashMap<>( );
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue <Map.Entry<Integer,Integer>> queue =new PriorityQueue<>(k,(x1,x2)->x2.getValue().compareTo(x1.getValue()));//大顶堆
        for(Map.Entry entry:map.entrySet()){
            queue.add(entry);
        }
        int []res=new int [k];
        for(int i=0;i<k;i++){
            res[i]=queue.poll().getKey();
        }
        return res;
    }

time complexity: O(nlogk) space complexity: O(n)

currybeefer commented 2 years ago

思路：参考官方题解，用priority_queue做，这个东西本质上是一个堆，这次构造一个小顶堆，然后只记录频率前k的数，最后输出代码：

    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        unordered_map<int,int> count;
        for(int i=0;i<nums.size();i++)
        {
            count[nums[i]]++;
        }

        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

        for(pair<int,int> son:count)
        {
            if(pq.size()!=k)
            {
                pq.push(make_pair(son.second,son.first));
            }
            else
            {
                if(son.second>pq.top().first)
                {
                    pq.pop();
                    pq.push(make_pair(son.second,son.first));
                }
            }
        }

        vector<int> res;
        while(pq.size())
        {
            res.push_back(pq.top().second);
            pq.pop();
        }
         return vector<int>(res.rbegin(), res.rend());
    }

复杂度: 时间复杂度：O(nlogk) k为k的长度空间复杂度：O(n)

webcoder-hk commented 2 years ago

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnts,heap = {},[]
        for n in nums:
            cnts[n] = cnts.get(n, 0)+1
        for n in cnts.keys():
            heappush(heap, (cnts[n], n))
            if len(heap)>k:
                heappop(heap)
        return [t[1] for t in heap]

time: O(n*logn) space: O(n)

ha0cheng commented 2 years ago

思路： 1.哈希表 + 桶排序使用哈希表来存储各个数字的计数，然后使用桶排序来找到前k个出现次数最多的数字，用一个大小为N的数组来存储排序数字，下标即是出现次数，然后从后向前取到长度等于k的结果就可以。

复杂度分析时间复杂度： O(N), 因为统计和桶排序的复杂度均为O(N)，最后取结果复杂度是O(k)，所以为O(N) 空间复杂度：O(N)，哈希表和桶的大小为N，所以为O(N)

哈希表+堆排序同样使用哈希表来存储计数，然后排序时得到一个大小为k的小顶堆，每次访问一个哈希表的计数，判断是否比小顶堆的最小值小，如果不是则插入，这样最后的结果就是小顶堆的所有元素。

复杂度分析：时间复杂度：O(Nlogk), 每次在一个大小为k的小顶堆插入元素的复杂度是O(logk) 空间复杂度：O(N), 哈希表，大小为O(N), 最小顶，大小为O(k)

桶排序代码如下：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            if num in count:
                count[num] += 1
            else:
                count[num] = 1

        Bucket = [[] for _ in range(len(nums))]

        for i in count.keys():
            Bucket[count[i]-1].append(i)
        Result = []
        i = len(nums)-1
        while len(Result)<k:
            Result.extend(Bucket[i])
            i -= 1
        return Result

最小堆排序代码如下：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            if num in count:
                count[num] += 1
            else:
                count[num] = 1

        heap = []
        for key, val in count.items():
            if len(heap) >= k:
                if val > heap[0][0]:
                    heapq.heapreplace(heap, (val, key))
            else:
                heapq.heappush(heap, (val, key))
        return [item[1] for item in heap]

bolunzhang2021 commented 2 years ago

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        // 根据map的value值正序排，相当于一个小顶堆
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            result[i] = queue.poll().getKey();
        }
        return result;
    }
}

wychmod commented 2 years ago

思路

先使用dic储存数组中每个数的频次，然后将dic排序。

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        for num in nums:
            dic[num] = dic.get(num, 0) + 1

        result = sorted(dic.items(), key=lambda x:x[1], reverse=True)
        ans = []
        for i in range(k):
            ans.append(result[i][0])
        return ans

复杂度分析

时间复杂度 Onlogn （n为数组种类）空间复杂度 On（n为数组种类）

KennethAlgol commented 2 years ago

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> counter = new HashMap<>();
    PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            Map.Entry.<Integer, Integer>comparingByValue());

    for (int num : nums) {
        counter.putIfAbsent(num, 0);
        counter.put(num, counter.get(num) + 1);
    }
    for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = pq.poll().getKey();
    }
    return result;
}

KennethAlgol commented 2 years ago

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        //桶排序
        //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
        List<Integer>[] list = new List[nums.length+1];
        Set<Map.Entry<Integer,Integer>> ms = map.entrySet();
        for (Map.Entry entry :ms) {
            int key = (int)entry.getKey();
            int i = map.get(key);
            if(list[i] == null){
                list[i] = new ArrayList();
            }
            list[i].add(key);
        }

        List<Integer> res = new ArrayList();
        // 倒序遍历数组获取出现顺序从大到小的排列
        for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
            if(list[i] == null) continue;
            res.addAll(list[i]);
        }
        int[] out = new int[res.size()];
        for(int a = 0; a < res.size(); a++){
            out[a] = res.get(a);
        }
        return out;
    }
}

zhulin1110 commented 2 years ago

题目地址(347. 前 K 个高频元素)

https://leetcode-cn.com/problems/top-k-frequent-elements/

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

 

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

思路

哈希表存储元素和元素出现的次数

数组排序返回出现频率前 k 高的元素

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = new Map(), arr = [...new Set(nums)]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })

    return arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k);
};

Ellie-Wu05 commented 2 years ago

思路一：count the frequency and sort the frequency to value list, trturn top k item

代码

from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        if k ==len(nums):
            return nums

        count = Counter(nums)

        new_count = sorted([(freq,key) for key,freq in count.items()],reverse=True)[:k]

        return [key for freq,key in new_count]

复杂度

时间：Onlogn 空间：On

tensorstart commented 2 years ago

思路

哈希表+sort

代码

var topKFrequent = function(nums,k) {
    let map=new Map;
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            let curValue=map.get(nums[i]);
            map.set(nums[i],++curValue);
        }else {
            map.set(nums[i],1);
        }
    }
    let mapArr=[];
    for(let entry of map){
        mapArr.push(entry)
    }
    mapArr=mapArr.sort((a,b)=>{
        return b[1]-a[1];
    })
    let res=[];
    for (let i = 0; i < k; i++) {
        res.push(mapArr[i][0]);
    }
    return res;
};

577961141 commented 2 years ago

347. 前 K 个高频元素

题目链接

https://leetcode-cn.com/problems/top-k-frequent-elements/

题目思路

因为加班，暂时用PHP内置的函数来使用，后续补回来

题目的题解code

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function topKFrequent($nums, $k) {
        $hashtable = [];

        foreach ($nums as $val) {
            if (!isset($hashtable[$val])) {
                $hashtable[$val] = 1;
            }else {
                $hashtable[$val] += 1;
            }
        }
        arsort($hashtable);

        return array_keys(array_slice($hashtable, 0, $k, true));
    }
}

时间和空间复杂度

时间复杂度：O(N) 空间复杂度：O(N)

sallyrubyjade commented 2 years ago

思路

利用map储存每个数字出现的频率，然后将map转成数组进行排序，截取排序后的前k的元素即是结果。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) {
            map.set(nums[i], 1);
        }else {
             map.set(nums[i], map.get(nums[i]) + 1);
        }
    }
    let sorted = Array.from(map).sort((a, b) => b[1] - a[1]);

    return sorted.slice(0, k).map(n => n[0]);
};

weihaoxie commented 2 years ago

思路

用哈希表存储每个数值及其出现的个数

对出现次数进行排序，取前k个

代码

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    d = dict()
    for n in nums:
        if n in d:
            d[n]+=1
        else:
            d[n] = 1
    new_d = sorted(d.items(),key=lambda x:x[1],reverse=True)
    return [item[0] for item in new_d[:k]]

复杂度

时间复杂度O(nlogn)
空间复杂度O(n)

xiayuhui231 commented 2 years ago

题目

前K个高频元素 https://leetcode-cn.com/problems/top-k-frequent-elements/submissions/

思路

将数组插入到map中，并统计次数。利用小顶堆排序，将前k个值存入数组中输出

代码

class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(auto x:nums) map[x]++;

        priority_queue<pair<int,int>, vector<pair<int, int>>, mycomparison> pri_que;

        for(unordered_map<int,int>::iterator it = map.begin(); it != map.end(); it++){
            pri_que.push(*it);
            if(pri_que.size() > k){
                pri_que.pop();
            }
        }
        vector<int>res(k);
        for(int i = k-1;i>=0;i--){
            res[i] = pri_que.top().first;
            pri_que.pop();
        }
        return res;
    }
};

复杂度：

时间复杂度：O(N) 空间复杂度：O(N)

testeducative commented 2 years ago


class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res(k, 0);
        unordered_map<int, int> m;
        for(auto &num : nums){
            m[num]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> q;
        for(auto node : m){
            pair<int, int> tmp;
            tmp = make_pair(node.second, node.first);
            q.push(tmp);
        }
        for(int i = 0;i<k;i++){
            auto p = q.top();
            q.pop();
            res[i] = p.second;
        }
        return res;
    }
};

leetcode-pp / 91alg-7-daily-check

【Day 20 】2022-04-20 - 347. 前 K 个高频元素 #23

347. 前 K 个高频元素

入选理由

题目地址

前置知识

题目描述

Ideas

Complexity

Idea

Code

Complexity

Code

Complexity

思路

代码

思路

代码

复杂度

Idea

Code

Complexity:

Day20 思路

复杂度分析

思路

复杂度

代码

思路

代码

复杂度分析

时间复杂度

空间复杂度

反思

思路 2 - 快速排序

代码

复杂度分析

时间复杂度

空间复杂度

思路

代码

复杂度分析

思路

代码

Problem 347. Top K Frequent Elements

Algorithm

Complexity

Code

思路

代码

【Day 20】347.Top K Frequent Elements「前 K 个高频元素」

题目描述

前置知识

思路

代码

复杂度分析

Idea

Code

Idea

Code

Complexity

代码

代码

Idea

Code

Time & Space Complexity

347. top-k-frequent-elements

Solution

Complexity

Code

思路

代码

复杂度分析

思路

代码

复杂度

Idea

Code

Complexity

Idea

Code