347. 前 K 个高频元素

题目链接：https://leetcode.cn/problems/top-k-frequent-elements/description/我的思路乍一看这题好像还挺简单的，找到前K个高频元素，那么很自然可以想到先统计每个元素的出现频率，然后再排序，输出前K个频率最高的即可。直接暴力求解：1. count = [[num, nums.count(num)] for num in set(nums)] 统计元素出现频率，和元素一起放到count列表中；2. count = sorted(count, key = lambda x: x[1], reverse = True) 按频次从大到小排序；3. return [x[0] for x in count[:k]] return排序好的count数组的前k个元素即可。但显然这不是最优解，这样的算法时间复杂度为$O(N\log n)$，对于特别长的序列，耗时特别久，最终结果为1378ms，也是第一次见到这么久的解题过程。那么显然要想提高时间和内存表现的话，就必须采用其他的降低复杂度的算法。纠正这里用“顶堆法”，会很方便和快捷，大幅度提高时间

排序 · 06-17

215. 数组中的第k个最大元素

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/我的思路又是一道中等题目的题，并且今天也是才学排序算法，因此拿到这题还是有点发怵，除了最基本的用排序方法外没有什么别的思路，但这样的时间复杂度不符合题意，所以还是要想别的办法。题解：快速选择法核心包括两部分，哨兵划分和递归哨兵：随机取数组中的一个数作为基准数（最左、最右或者随机取），之后遍历剩下的元素，把小于基准数的放到哨兵的左边，大于的放到哨兵的右边递归：继续对左子数组和右子数组执行哨兵划分，直到子数组的长度为1时终止以上过程可以用题解的图来很好解释：放到算法层面，我们可以定义三个列表来实现上述操作：small, equal和big，把和pivot相等的值放进equal，更小的放进small，更大的放进big，这样一来我们就得到了这个数组中前len(big)大的数字，执行完放数字操作后比较len(big)和k的大小：如果len(big) < k，说明我们的pivot选得刚好（我们想要的值全都在equal里）或者选大了（我们想

排序 · 06-09