347. 前 K 个高频元素 好

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

• topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogk
• 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。
• 求前 k 大，用小根堆，求前 k 小，用大根堆。

//引入快排，哈希表计算频率，排序后输出
import "sort"
func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    s := make([]int,0)
    for _,v := range nums {
        i,ok := m[v]
        if ok {
            m[v] = i+1
        }else{
            m[v] = 1
            s = append(s, v)
        }
    }
    sort.Slice(s, func(i, j int) bool {
        return m[s[i]] > m[s[j]]
    })
    return s[:k]
}

//桶排序法，时空On
func topKFrequent(nums []int, k int) []int {
    keymap:=make(map[int]int)
    maxn:=    math.MinInt64

    for _,i:=range nums{
        if _,ok:=keymap[i];ok{
            keymap[i]++
        }else{
            keymap[i]=1
        }
        if keymap[i]>maxn{
            maxn=keymap[i]
        }
    }

    hashtop:=make([][]int,maxn+1)
    for key,val:=range keymap{
        hashtop[val]=append(hashtop[val],key)
    }

    res:=make([]int,0)
    for i:=maxn;i>=0;i--{
        res=append(res,hashtop[i]...)
        k-=len(hashtop[i])
        if k==0{
            break
        }
    }

    return res
}

官方解答：我也不会，排序太难了

//快排选择算法：平均时间On，空间On
func topKFrequent(nums []int, k int) []int {
    occurrences := map[int]int{}
    for _, num := range nums {
        occurrences[num]++
    }
    values := [][]int{}
    for key, value := range occurrences {
        values = append(values, []int{key, value})
    }
    ret := make([]int, k)
    qsort(values, 0, len(values) - 1, ret, 0, k)
    return ret
}

func qsort(values [][]int, start, end int, ret []int, retIndex, k int) {
    rand.Seed(time.Now().UnixNano())
    picked := rand.Int() % (end - start + 1) + start;
    values[picked], values[start] = values[start], values[picked]

    pivot := values[start][1]
    index := start

    for i := start + 1; i <= end; i++ {
        if values[i][1] >= pivot {
            values[index + 1], values[i] = values[i], values[index + 1]
            index++
        }
    }
    values[start], values[index] = values[index], values[start]
    if k <= index - start {
        qsort(values, start, index - 1, ret, retIndex, k)
    } else {
        for i := start; i <= index; i++ {
            ret[retIndex] = values[i][0]
            retIndex++
        }
        if k > index - start + 1 {
            qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1))
        }
    }
}

//堆排：用小顶堆时间Nlogk，空间On；大顶堆Nlogn
func topKFrequent(nums []int, k int) []int {
    occurrences := map[int]int{}
    for _, num := range nums {
        occurrences[num]++
    }
    h := &IHeap{}
    heap.Init(h)
    for key, value := range occurrences {
        heap.Push(h, [2]int{key, value})
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    ret := make([]int, k)
    for i := 0; i < k; i++ {
        ret[k - i - 1] = heap.Pop(h).([2]int)[0]
    }
    return ret
}

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
}