LeetCode 347. Top K Frequent Elements

elva 发布于2019-07-31 10:16 / 3355人阅读

摘要：描述给定一个非空的整数数组，返回其中出现频率前高的元素。然后以元素出现的次数为值，统计该次数下出现的所有的元素。从最大次数遍历到次，若该次数下有元素出现，提取该次数下的所有元素到结果数组中，知道提取到个元素为止。

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

源代码文件在这里。
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

云服务器混合云 Frequent Elements LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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