Loading...
墨滴

公众号:offer多多

2021/09/29  阅读:24  主题:橙心

图解算法:【Day 20】347. 前 K 个高频元素

【Day 20】347. 前 K 个高频元素

题目:

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

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

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

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

  • 难度:中等

思路描述

思路1. 第一个感觉 排序 然后统计前面k个不同的元素。【卡住】

细节是魔鬼:大小排序 和元素重复关系 不是太大

  • 难点:

a. 如何对map的value进行排序呢 这个不好实现?

思路2. 在方法1基础:利用堆排序

复杂度分析

  • 时间复杂度:O(Nlogk),

其中 N 为数组的长度。我们首先遍历原数组,并使用哈希表记录出现次数,每个元素需要 O(1) 的时间,共需 O(N)) 的时间。

随后,我们遍历「出现次数数组」,由于堆的大小至多为 k

  • 空间复杂度:O(N)。 哈希表的大小为 O(N),而堆的大小为 O(k),共计为 O(N)。

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路3. 在方法1基础:利用快速排序

细节是魔鬼:时间复杂度

  • 原版的快速排序算法的平均时间复杂度为 O(NlogN)。
  • 我们的算法中,每次只需在其中的一个分支递归即可,因此算法的平均时间复杂度降为 O(N)O(N)。

不同版本代码实现

c++

/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {

        //01 统计每个元素出现次数 time:o(n logn)
        map<int, int> counts;
        for (auto key : nums)
        {
            counts[key]++; //map key是有序的。但是value无法排序。 需要办法解决!
        }

        //02 为什么是小heap space:o(k)
        //假如 知道一个元素元素出现的频率,如果判断是否k个大,
        //只要和假设前面k个最小的一个比较就可以

        /**定义一下比较函数*/
        auto cmp = [](const pair<int, int> &a, const pair<int, int> &b) { return a.second > b.second; };
        // 定义优先级队列
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> minHeap(cmp);

        //03 求top k time:o(n logn)
        //https://www.cnblogs.com/developing/articles/10890903.htmlC++11新特性——for遍历
        for (auto &key : counts)
        {
            if (minHeap.size() < k)
            {
                minHeap.emplace(key.first, key.second);
            }
            else if (key.second > minHeap.top().second)
            {
                minHeap.pop();
                minHeap.emplace(key.first, key.second);
            }
        }

        //04 打印
        vector<int> ret;
        while (!minHeap.empty())
        {
            int temp = minHeap.top().first;
            minHeap.pop();
            ret.push_back(temp);
        }

        return ret;
    }
};

go

//方法一:小顶堆
func topKFrequent(nums []int, k int) []int {
    map_num:=map[int]int{}
    //记录每个元素出现的次数
    for _,item:=range nums{
        map_num[item]++
    }
    h:=&IHeap{}
    heap.Init(h)
    //所有元素入堆,堆的长度为k
    for key,value:=range map_num{
        heap.Push(h,[2]int{key,value})
        if h.Len()>k{
            heap.Pop(h)
        }
    }
    res:=make([]int,k)
    //按顺序返回堆中的元素
    for i:=0;i<k;i++{
        res[k-i-1]=heap.Pop(h).([2]int)[0]
    }
    return res
}

//构建小顶堆
type IHeap [][2]int

func (h IHeap) Len()int {
    return len(h)
}

func (h IHeap) Less (i,j int) bool {
    return h[i][1]<h[j][1]
}

func (h IHeap) Swap(i,j int) {
    h[i],h[j]=h[j],h[i]
}

func (h *IHeap) Push(x interface{}){
    *h=append(*h,x.([2]int))
}
func (h *IHeap) Pop() interface{}{
    old:=*h
    n:=len(old)
    x:=old[n-1]
    *h=old[0:n-1]
    return x
}


//方法二:利用O(logn)排序
func topKFrequent(nums []int, k int) []int {
    ans:=[]int{}
    map_num:=map[int]int{}
    for _,item:=range nums {
        map_num[item]++
    }
    for key,_:=range map_num{
        ans=append(ans,key)
    }
    //核心思想:排序
    //可以不用包函数,自己实现快排
    sort.Slice(ans,func (a,b int)bool{
        return map_num[ans[a]]>map_num[ans[b]]
    })
    return ans[:k]
}

作者:carlsun-2
链接:https://leetcode-cn.com/problems/top-k-frequent-elements/solution/dai-ma-sui-xiang-lu-347-qian-kge-gao-pin-efgx/
来源:力扣(LeetCode)
  • 快速排序
func topKFrequent(nums []int, k int) []int {
 nHash := map[int]int{}
 for i := 0; i < len(nums); i++ {
  nHash[nums[i]]++
 }

 nfs := nfqs{}
 for v, n := range nHash {
  nfs = append(nfs, nf{v: v, n: n})
 }

 quickSelect(nfs, k)

 res := make([]int, k)
 for i := 0; i < k; i++ {
  res[i] = nfs[len(nfs)-1-i].v
 }

 return res
}

type nf struct {
 v int
 n int
}

type nfqs []nf

func (v nfqs) Len() int {
 return len(v)
}

func (v nfqs) Less(i, j int) bool {
 return v[i].n < v[j].n
}
func (v nfqs) Swap(i, j int) {
 v[i], v[j] = v[j], v[i]
 return
}

// QuickSelectInterface 快选接口
type QuickSelectInterface interface {
 Len() int
 Less(i, j intbool
 Swap(i, j int)
}

func quickSelect(items QuickSelectInterface, topK int) {
 _quickSelect(items, 0, items.Len()-1, topK)
 return
}

func _quickSelect(items QuickSelectInterface, s int, e int, k int) {
 l := e - s + 1
 if l <= 1 {
  return
 }

 m := s

 for i := s; i < e; i++ {
  if items.Less(i, e) {
   items.Swap(i, m)
   m++
  }
 }
 items.Swap(m, e)

 if items.Len()-k == m {
  return
 } else if items.Len()-k > m {
  _quickSelect(items, m+1, e, k)
 } else {
  _quickSelect(items, s, m-1, k)
 }
}

作者:hills
链接:https://leetcode-cn.com/problems/top-k-frequent-elements/solution/li-yong-si-xiang-de-jie-fa-by-hills/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

公众号:offer多多

2021/09/29  阅读:24  主题:橙心

作者介绍

公众号:offer多多