leetcode-mid-sorting and searching -347. Top K Frequent Elements

mycode 71.43%

class Solution(object):

    def topKFrequent(self, nums, k):

        """

        :type nums: List[int]

        :type k: int

        :rtype: List[int]

        """

        if not nums:

            return []

        from collections import Counter

        s = Counter(nums).most_common()

        res = []

        for val,count in s:

            res.append(val)

            if len(res) == k:

                return res

参考：

思路：

heapq--该模块提供了堆排序算法的实现。堆是二叉树，最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。

如果需要获取堆中最大或最小的范围值，则可以使用heapq.nlargest() 或heapq.nsmallest() 函数

下面例子中heapq.nlargest的第二个参数遍历，每一个值代入第三个参数中，得到最终用来排序的数组成的列表

import heapq

from pprint import pprint

portfolio = [

    {'name': 'IBM', 'shares': 100, 'price': 91.1},

    {'name': 'AAPL', 'shares': 50, 'price': 543.22},

    {'name': 'FB', 'shares': 200, 'price': 21.09},

    {'name': 'HPQ', 'shares': 35, 'price': 31.75},

    {'name': 'YHOO', 'shares': 45, 'price': 16.35},

    {'name': 'ACME', 'shares': 75, 'price': 115.65}

]

cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])

expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

pprint(cheap)

pprint(expensive)

"""

输出：

[{'name': 'YHOO', 'price': 16.35, 'shares': 45},

 {'name': 'FB', 'price': 21.09, 'shares': 200},

 {'name': 'HPQ', 'price': 31.75, 'shares': 35}]

[{'name': 'AAPL', 'price': 543.22, 'shares': 50},

 {'name': 'ACME', 'price': 115.65, 'shares': 75},

 {'name': 'IBM', 'price': 91.1, 'shares': 100}]

遍历每个key，作为第三个参数的参数，得到对应的值，他们组合了用来排序的所有值

import heapq

class Solution(object):

    def topKFrequent(self, nums, k):

        """

        :type nums: List[int]

        :type k: int

        :rtype: List[int]

        """

        if not k:

            return 0

        mydict={}

        for i in nums:

            if i in mydict:

                mydict[i]+=1

            else:

                mydict[i]=0

        return heapq.nlargest(k,mydict.keys(),mydict.get)

巴特西

leetcode-mid-sorting and searching -347. Top K Frequent Elements

最新文章

热门文章