说一道排序题

很经典的排序问题 (๑• . •๑)

先看题目,“前K个高频元素”

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

简单解法

这题很简单,两步:

  1. 用字典保存数字及其出现的对应频率
  2. 排序

那么第一步就不用说了,很简单

m = dict()
for num in nums:
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

有趣的就在第二步,排序。很多人都是使用内置库sorted

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        m = dict()
        for num in nums:
            if num in m:
                m[num] += 1
            else:
                m[num] = 1

        output = sorted(m.items(), key=lambda e: e[1], reverse=True)

        final = []
        for i in range(k):
            final.append(output[i][0])
        return final

最简洁的代码是直接使用Python内置的collections

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        import collections
        counter = collections.Counter(nums)
        return [item[0] for item in counter.most_common(k)]

这真是是我们想要的吗?并不是。我们的目标是不使用任何内置库。

sorted原理

关于Python的sorted排序算法,这篇文章讲的比较详细:python sort函数内部实现原理,说到Python使用的是著名的Timesort算法。

Timsort是结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法,它在现实中有很好的效率。

Tim Peters在2002年设计了该算法并在Python中使用(TimSort 是 Python 中 list.sort 的默认实现)。该算法找到数据中已经排好序的块-分区,每一个分区叫一个run,然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序,现在Java SE7和Android也采用Timsort算法对数组排序。

如果想自己用Python来写一个排序算法,完成本题要求该如何写?也就是对这个字典进行排序,{5: 1, 1: 3, 4: 1, 2: 2, 3: 1},有什么好办法。

思路可以是两个指针遍历字典,如果左边大于右边,则替换位置。

更好的方法

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        m = dict()
        for num in nums:
            if num in m:
                m[num] += 1
            else:
                m[num] = 1
        bucket = [[] for _ in range(len(nums) + 1)]

        for key, value in m.items():
            bucket[value].append(key)

        result = []
        for i in range(len(nums), 0, -1):
            for n in bucket[i]:
                result.append(n)
                if len(result) == k:
                    return result
        return result

很巧妙的使用列表的索引来保存value。

此时bucket值是[[], [5, 4, 3], [2], [1], [], [], [], [], []],索引即出现次数。

此解法用时72ms,战胜 50.84 % 的 python3 提交记录。但是看了排在前面的算法,都是使用的Python内置的collections

如果是你,会用什么方法呢?

原文发布于微信公众号 - Python爬虫与算法进阶(zhangslob)

原文发表时间:2018-11-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

KMP(4)

15250
来自专栏五分钟学算法

五分钟弄懂有点难度的排序:堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

16840
来自专栏海天一树

AtCoder入门练习题B--题解报告

一、题目 https://practice.contest.atcoder.jp/tasks/practice_2 二、分析 这里有三组测试用例。 第一组N =...

33480
来自专栏恰童鞋骚年

剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面

  例如有以下一个整数数组:12345,经过调整后可以为:15342、13542、13524等等。

12660
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

10110
来自专栏五分钟学算法

五分钟看懂一个高难度的排序:堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

11820
来自专栏chenjx85的技术专栏

leetcode-58-Length of Last Word

22160
来自专栏章鱼的慢慢技术路

浅谈main(),int main(),void main(),int main(void)四者之间的区别

13830
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

43360
来自专栏codingforever

经典算法巡礼(四) -- 排序之希尔排序

希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。

7420

扫码关注云+社区

领取腾讯云代金券