亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LeetCode] Top K Frequent Elements

jkyin / 2870人閱讀

Problem

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

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.

Solution 
public class Solution {
    public List topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map map = new HashMap<>();
        for (int num: nums) {
            if (map.containsKey(num)) map.put(num, map.get(num)+1);
            else map.put(num, 1);
        }
        List[] freq = new ArrayList[n+1];
        for (int num : map.keySet()) {
            int i = map.get(num);
            if (freq[i] == null) {
                freq[i] = new ArrayList<>();
            }
            freq[i].add(num);
        }
        List res = new ArrayList<>();
        for (int index = freq.length - 1; index >= 0 && res.size() < k; index--) {
            if (freq[index] != null) {
                res.addAll(freq[index]);
            }
        }
        return res;
    }
}
Update 2018-9 PriorityQueue 
class Solution {
    public List topKFrequent(int[] nums, int k) {
        List res = new ArrayList<>();
        if (nums == null || nums.length < k) return res;
        Map map = new HashMap<>();
        PriorityQueue> queue = new PriorityQueue<>((a, b)->b.getValue()-a.getValue());
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        for (Map.Entry entry: map.entrySet()) {
            queue.offer(entry);
        }
        int count = 0;
        while (count < k) {
            Map.Entry entry = queue.poll();
            res.add(entry.getKey());
            count++;
        }
        return res;
    }
}
Bucket sort 
class Solution {
    public List topKFrequent(int[] nums, int k) {
        List res = new ArrayList<>();
        if (nums == null || nums.length < k) return res;
        Map map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        List[] buckets = new ArrayList[nums.length+1];
        for (Map.Entry entry: map.entrySet()) {
            int value = entry.getValue();
            if (buckets[value] == null) buckets[value] = new ArrayList<>();
            buckets[value].add(entry.getKey());
        }
        for (int i = buckets.length-1; i >= 0 && res.size() < k; i--) {
            if (buckets[i] != null) res.addAll(buckets[i]);
        }
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/65995.html

相關(guān)文章

  • LeetCode 347. Top K Frequent Elements

    摘要：描述給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前高的元素。然后以元素出現(xiàn)的次數(shù)為值，統(tǒng)計該次數(shù)下出現(xiàn)的所有的元素。從最大次數(shù)遍歷到次，若該次數(shù)下有元素出現(xiàn)，提取該次數(shù)下的所有元素到結(jié)果數(shù)組中，知道提取到個元素為止。 Description Given a non-empty array of integers, return the k most frequent elements. E...

    elva 評論0 收藏0

  • leetcode347. Top K Frequent Elements

    摘要：題目要求假設(shè)有一個非空的整數(shù)數(shù)組，從中獲得前個出現(xiàn)頻率最多的數(shù)字。先用來統(tǒng)計出現(xiàn)次數(shù)，然后將其丟到對應(yīng)的桶中，最后從最高的桶開始向低的桶逐個遍歷，取出前個頻率的數(shù)字。 題目要求 Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,...

    imccl 評論0 收藏0

  • [LeetCode] Top K Frequent Elements [HashMap/Heap/T

    摘要：先按照元素次數(shù)的將所有元素存入，再按照次數(shù)元素將哈希表里的所有元素存入，然后取最后的個元素返回。 Problem 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: ...

    AaronYuan 評論0 收藏0

  • [LeetCode/LintCode] Top K Frequent Words

    LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

    0x584a 評論0 收藏0

  • 程序員進階之算法練習(xí)：LeetCode專場

    摘要：例如題目解析題目的意思很明顯，就是把兩個數(shù)字加起來，需要考慮進位的情況?？偨Y(jié)這個題目如果都能獨立完成，那么水平已經(jīng)可以足以應(yīng)付國內(nèi)各大企業(yè)的算法面。 歡迎大家前往騰訊云+社區(qū)，獲取更多騰訊海量技術(shù)實踐干貨哦~ 本文由落影發(fā)表 前言 LeetCode上的題目是大公司面試常見的算法題，今天的目標(biāo)是拿下5道算法題： 題目1是基于鏈表的大數(shù)加法，既考察基本數(shù)據(jù)結(jié)構(gòu)的了解，又考察在處理加法過程中...

    MrZONT 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<