LeetCode 347. Top K Frequent Elements

elva 發布于2019-07-31 10:16 / 3527人閱讀

摘要：描述給定一個非空的整數數組，返回其中出現頻率前高的元素。然后以元素出現的次數為值，統計該次數下出現的所有的元素。從最大次數遍歷到次，若該次數下有元素出現，提取該次數下的所有元素到結果數組中，知道提取到個元素為止。

Description

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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:

Input: nums = [1], k = 1
Output: [1]
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:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:

輸入: nums = [1], k = 1
輸出: [1]
說明：

你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
你的算法的時間復雜度必須優于 O(n log n) , n 是數組的大小。

思路

使用字典，統計每個元素出現的次數，元素為鍵，元素出現的次數為值。

然后以元素出現的次數為值，統計該次數下出現的所有的元素。

從最大次數遍歷到 1 次，若該次數下有元素出現，提取該次數下的所有元素到結果數組中，知道提取到 k 個元素為止。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-09 12:37:36
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-09 15:57:00

from collections import Counter


class Solution:
    def topKFrequent(self, nums: [int], k: int) -> [int]:
        # 桶
        bucket = dict()
        # 構建字典，鍵位數字，值為該數字出現過的次數
        table = Counter(nums)
        result, count = [], 0
        # 以元素出現的次數位鍵，該次數下的所有元素構成的 List 為值
        for num, times in table.items():
            if times not in bucket: bucket[times] = []
            bucket[times].append(num)
        # 出現的最大次數
        maxtime = max(table.values())

        for time in range(maxtime, 0, -1):
            # 如果該次數下有元素
            if time in bucket:
                # 提取當前次數下的所有元素到結果中
                result.extend(bucket[time])
                count += len(bucket[time])
            if count == k: break
        return result

源代碼文件在這里。
?本文首發于何睿的博客，歡迎轉載，轉載需保留文章來源，作者信息和本聲明.

云服務器 GPU云服務器 Frequent Elements LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43555.html

leetcode347. 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,...

imccl 2019-08-15 15:54 評論0 收藏0
[LeetCode] Top K Frequent Elements

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 e...

jkyin 2019-08-14 15:45 評論0 收藏0
[LeetCode] Top K Frequent Elements [HashMap/Heap/T

摘要：先按照元素次數的將所有元素存入，再按照次數元素將哈希表里的所有元素存入，然后取最后的個元素返回。 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 2019-08-14 15:56 評論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 2019-08-15 13:32 評論0 收藏0
程序員進階之算法練習：LeetCode專場

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

MrZONT 2019-08-23 13:42 評論0 收藏0