Martyn Ye

A geek & a dreamer

  • 主页
  • 随笔
所有文章 友链 关于我

Martyn Ye

A geek & a dreamer

  • 主页
  • 随笔

[LeetCode] Top K Frequent Elements

2016-05-03

Analysis:

We can construct a mini-heap of size K, please pay attention to the tuple of the heap, the key should be the counter.

Time Complexity:

  • O(nlogk)

Space Complexity:

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
d = collections.defaultdict(int)
for t in nums:
d[t] += 1

h = []
for key, v in d.iteritems():
if len(h) < k:
heapq.heappush(h, (v, key))
else:
hv, hk = h[0]
if hv < v:
heapq.heapreplace(h, (v, key))
output = []
while len(h) > 0:
v, key = heapq.heappop(h)
output.append(key)
output.reverse()
return output
赏

谢谢你请我吃糖果

  • LeetCode
  • Heap
  • Heap Sort

扫一扫,分享到微信

微信分享二维码
[LeetCode] Peeking Iterator
[LeetCode] Maximum Product of Word Lengths
© 2024 Martyn Ye
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链
  • 关于我

tag:

  • Misc
  • LeetCode
  • Dynamic Programming
  • Binary Tree
  • Greedy
  • Breadth First Search
  • Binary Search
  • Math
  • System Design
  • Binary Search Tree
  • Backtracking
  • Heap
  • Design
  • Depth First Search
  • Build Binary Tree
  • array
  • Tree
  • Stack
  • Reservoir Sampling
  • Bit Manipulation
  • Deep-First-Search
  • Trie
  • Hash Table
  • Two Pointers
  • String
  • Android
  • Github
  • Data Structure Design
  • C++
  • Sort
  • Linked List
  • Bit-Manipulation
  • LintCode
  • Merge Sort
  • Mafia fight
  • Array
  • Heap Sort
  • Open Source
  • Summary

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

Martyn's Playground