[LeetCode]347. Top K Frequent Elements 排名前K个最经常出现的元素

题目地址:

https://leetcode.com/problems/top-k-frequent-elements/

题目描述:

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

题目大意:

给你一个非空整型数组,返回前k个最频繁出现的元素。

比如说,

给你[1,1,1,2,2,3] 和  k = 2, 返回 [1,2].

注意:

  • 你可以假设一个k是固定的,1 ≤ k ≤ number 个独一无二的元素。
  • 你的算法复杂度一定要比O(n log n)还要好,其中n是这个数组的长度。

 

我不得不承认一开始对题目会错意了。因为谷歌翻译告诉我:“考虑到整数的非空数组,返回k个最常见的元素。”,然后百度翻译告诉我:“给定一个非空的整数数组,返回k个最频繁的元素。”他们这个意思都没有说要排序,然后当我被Wrong answer的时候才知道会错了意。英文真是尴尬。意思是返回前 k 个频繁出现的元素。

频繁出现,那就意味着要用哈希容器去存进去,因为哈希容器  unordered_map<int,int> 中每次存进去之前可以用里面的 find() 方法作一次查找。如果找到了,就把 value 的值+1,没找到,就赋值为 1 。这样其实就能让这个最后用来查找的表格里没有重复的 key ,并且存储他的value。

但是 map 是不会排序的。所以我们需要把它丢进一个 vector 容器中去调用 C++ 自己的那个 sort 方法,来进行排序。

需要注意的是,sort()方法有三个参数,前两个是排序的首尾,第三个参数是用来判断的函数。这个是自定义的。需要注意的是它应该作为静态函数来调用。然后就是说,如果后面这个判断函数为真,就不做排序,如果为假才调换顺序。(这是我的理解,因为文档看得很晕。)

我 Accept 的代码:(原本以为只能打败 10% 的人,后来打败了 33% 的人。48ms)


找来找去找来找去,他们写的代码怎么都比我长。。 最后找到用 Java 写的前辈。

答案地址:http://www.joyhwong.com/2016/05/06/leetcode-347-top-k-frequent-elements/

“(引用)

使用Java的容器类——映射——将数组中的元素统计出个数,然后自己现实一个含有Key和Value的实现了Comparable的类,按照Value排序,最后将前k个Key输出。

我觉得那个 Collections.sort()函数很厉害。感觉 Java 会比 C++ 更友好一些。不过要学的包好多。

评论已关闭。