6

Leetcode 347.Top K Frequent Elements | XINDOO

 2 years ago
source link: https://zxs.io/article/800
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Leetcode 347.Top K Frequent Elements
当前位置:XINDOO > 算法 > 正文

Top K Frequent Elements
  一句话理解题意:输出数组中出现次数对多的k个数。
  在如果用C语言来写这个题目,思路就是先按数的大小排序,然后再用一个结构体数组保存每个数的出现次次数。 因为数组已经有序了,所以只需要遍历一次数组就可以获得每个数的出现次数了。 结构体如下

strut node 
{
    int num;       //保存数组中的数
    int count;     //这个数出现的次数
}

  然后对这个结构体数组按照count由大到小排序,返回前k个,此题得解。 如果我们排序都用快速排序,最终的时间复杂度是O(nlogn)+O(nlogn)+O(n),还是O(n*logn),符合题目要求。 但如果使用C语言,我们需要自己写排序算法,自己去开考虑很多细节,而改用Java的话,java自带的各种库函数将大大简化本提的难度。
  我们用map来存储每个数和每个数出现次数的对于关系,然后直接调用Collections的sort方法对map list化后的集合排序,这里我们只需要重载下Comparator类的compare函数即可。 我的代码如下。

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<Integer>();
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        for (int num:nums) {
            if (map.containsKey(num))
                map.put(num,map.get(num)+1);
            else
                map.put(num,1);
        }
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        //因为无法对map容器做排序,所以先要将map转化为list。
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
                    @Override
                    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                        if (o1.getValue() == o2.getValue())
                            return o1.getKey() - o2.getKey();
                        return o2.getValue() - o1.getValue();
                    }
                }
        );
        int cnt = 0;
        for (Map.Entry<Integer,Integer> entry:list) {
            ans.add(entry.getKey());
            cnt++;
            if (cnt == k)
                break;
        }
        return ans;
    }
}

  这里用的map使用hash算法,计算每个数次数的时间复杂度从上文C实现版的O(nlogn)将到O(n),但排序的时间复杂度还是O(nlogn),从理论上看,总的时间复杂度是O(n)+O(nlogn),看起来要比C解法优。 但由于Java的各种封装和本身的特性,实际运行时间不一定会少于C的解法,开发便捷程度还是需要以效率来替换的。


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK