刷题笔记

A collection of 2 posts

刷题笔记

[LC] 347. 前 K 个高频元素

题目链接:https://leetcode-cn.com/problems/top-k-frequent-elements/ 题解该题的目的很简单,考察是堆排序,就是将遍历所有的元素,用一个hashmap记录所有出现元素的频数,最后从hashmap导出来一个个 < 数字,频数> 的元组,最后通过比较频数来获取最高频的几个元素,这样想想,用快排也不是不行的。 还是谈谈根排序吧,题目中要求的是前几个高频元素,那么我们就应该使用大根堆一个一个把数据拿出来? Naive! 题目中给到了提示: 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。如果你执行K次大根堆排序,那么时间复杂度不会优于 O(n log n) 。 那么可以反其道行之,使用小根堆。 如果使用小根堆,根元素是堆中最小值,那么,我们只需要固定住小根堆中的元素最大为K,并在向堆中插入元组(

  • Hafrans
刷题笔记

[LC] 60. 第k个排列

题目链接:https://leetcode-cn.com/problems/permutation-sequence/ 题目分析这个题目还是比较好做的,我思考了不长时间就想到问题的解决办法并一次性AC,但是代码写的太烂。。。 给出n个元素的集合,其所有元素共有 n! 种排列,当我们由小到大找第其第K个排列方式时,我们可以这样办: 先固定第一个数,那么剩下的数就有 (n - 1 )!种排列,根据第一个数的不同可以分为n组,其下标范围为 $$ { [ 0, (n - 1)! ), [(n - 1)!, 2*(n-1)!), ... , [(n-1)*(n-1)!, n!)} $$ 我们可以根据每一组的下标范围以及所要查找的第K个排列就可以明确知道它是归于哪一个组。 其实问题到这里就已经解决了,无非是一个递归问题,我们通过不断细化分组,将K定位于某一个组上,这样答案就得出来了。 代码// 60. 第k个排列

  • Hafrans