32ms golang solution


  • 0
    T
    type Node struct{
        value int
        cnt int
    }
    func NewNode(v,c int) *Node{
        return &Node{
            value: v,
            cnt: c,
        }
    }
    func topKFrequent(nums []int, k int) []int {
        arrlen := len(nums)
        hash := make(map[int]int)
        for i := 0; i < arrlen; i++{
            hash[nums[i]] += 1
        }
        heap := make([]*Node,k+1)
        for i := 0; i < k + 1; i++{
            heap[i] = NewNode(0,0)
        }
        for key,v := range hash {
            if v < heap[1].cnt{
                continue
            }
            heap[1] = NewNode(key,v)
            shif_down(heap,1,k)
        }
        arr := make([]int,k)
        cnt := k -1
        for ;cnt >= 0; cnt--{
            arr[cnt] = heap[1].value
            heap[1] = heap[k]
    		k--
            shif_down(heap,1,k)
        }
        return arr
    }
    func shif_down(A []*Node,s int, end int){
        i := s
        j := 2 * s;
        for j <= end {
            if j < end && A[j].cnt > A[j+1].cnt {
                j++
            }
            if(A[i].cnt <= A[j].cnt){
                break
            }
            A[i],A[j] = A[j],A[i]
            i = j
            j = 2 * j
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.