leetcode hot 100 前k个高平元素

347. 前 K 个高频元素

已解答

中等

相关标签

相关企业

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

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        def shift_up(heap , tmp):
            heap.append(tmp)
            child = len(heap)-1
            while child/2>0 and heap[child/2][1]>heap[child][1]:
                # 向上交换一个
                x=heap[child/2]
                heap[child/2] = heap[child]
                heap[child] = x
                child/=2
            



        def shift_down(heap):
            # 把左右子树里面较小的那个放到上面来
            parent =1 
            
            while parent*2  <= k  :
                if parent*2 == k:
                    child = parent*2
                else:
                    if heap[parent*2][1] > heap[parent*2+1][1]:
                        child = parent*2+1
                    else:
                        child = parent*2
                if heap[parent][1]>heap[child][1]:
                    # huan
                    # heap[parent] =heap[child]
                    x = heap[parent]
                    heap[parent] = heap[child]
                    heap[child] = x
                    parent = child
                else:
                    break
           
            
            

        heap=[(None,0)]

        frequency = {}
        frequency_list=[]
        for tmp in nums:
            if frequency.get(tmp)==None:
                frequency[tmp]=1
            else:
                frequency[tmp]+=1
        
        for tmp in frequency.keys():
            frequency_list.append((tmp,frequency[tmp]))


        # print(frequency_list)
        # 对于前k个数字，直接上浮
        for i in range(k):
            shift_up(heap,frequency_list[i])

        
        
        for i in range(k,len(frequency_list)):
            if frequency_list[i][1]>heap[1][1]:
                heap[1] = frequency_list[i]
                shift_down(heap)
                

        ans=[]
        for i in range(1,len(heap)):
            ans.append(heap[i][0])

        return ans

        

主要是要知道这里需要使用的是堆，而且求最大的几个就是最小堆，因为每次都是把最小的给扔出来，这样才是位置最大的几个。不需要最前面搞个空的东西其实