資訊專欄INFORMATION COLUMN
摘要：描述給定一個非空的整數(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.
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.
給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
說明：
你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個數(shù)。
你的算法的時間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小。
使用字典，統(tǒng)計每個元素出現(xiàn)的次數(shù)，元素為鍵，元素出現(xiàn)的次數(shù)為值。
然后以元素出現(xiàn)的次數(shù)為值，統(tǒng)計該次數(shù)下出現(xiàn)的所有的元素。
從最大次數(shù)遍歷到 1 次，若該次數(shù)下有元素出現(xiàn)，提取該次數(shù)下的所有元素到結(jié)果數(shù)組中，知道提取到 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()
# 構(gòu)建字典，鍵位數(shù)字，值為該數(shù)字出現(xiàn)過的次數(shù)
table = Counter(nums)
result, count = [], 0
# 以元素出現(xiàn)的次數(shù)位鍵，該次數(shù)下的所有元素構(gòu)成的 List 為值
for num, times in table.items():
if times not in bucket: bucket[times] = []
bucket[times].append(num)
# 出現(xiàn)的最大次數(shù)
maxtime = max(table.values())
for time in range(maxtime, 0, -1):
# 如果該次數(shù)下有元素
if time in bucket:
# 提取當(dāng)前次數(shù)下的所有元素到結(jié)果中
result.extend(bucket[time])
count += len(bucket[time])
if count == k: break
return result
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 ，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來源 ，作者信息和本聲明.
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/43555.html
摘要：題目要求假設(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,...
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...
摘要：先按照元素次數(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: ...
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...
摘要：例如題目解析題目的意思很明顯，就是把兩個數(shù)字加起來，需要考慮進位的情況。總結(jié)這個題目如果都能獨立完成，那么水平已經(jīng)可以足以應(yīng)付國內(nèi)各大企業(yè)的算法面。 歡迎大家前往騰訊云+社區(qū)，獲取更多騰訊海量技術(shù)實踐干貨哦~ 本文由落影發(fā)表 前言 LeetCode上的題目是大公司面試常見的算法題，今天的目標(biāo)是拿下5道算法題： 題目1是基于鏈表的大數(shù)加法，既考察基本數(shù)據(jù)結(jié)構(gòu)的了解，又考察在處理加法過程中...
閱讀 2331·2021-11-17 09:33
閱讀 858·2021-10-13 09:40
閱讀 586·2019-08-30 15:54
閱讀 789·2019-08-29 15:38
閱讀 2424·2019-08-28 18:15
閱讀 2487·2019-08-26 13:38
閱讀 1853·2019-08-26 13:36
閱讀 2140·2019-08-26 11:36
