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

4. 寻找两个正序数组的中位数

题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/我的思路这是一道困难级别的题，确实非常难，在时间复杂度的限制下，只能采用二分法来进行求解，关键是如何进行二分。自己拿到这题完全没有思路。题解官方题解给了两种办法，一种是直接双指针搜索，判断规则非常复杂，程序也很长，尽管时间复杂度表现很优秀，但还是有点难理解，这里复述另一种解法，切分的思路，因为我们要找的是中位数，统计中，中位数的作用是：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。假设两个序列的长度分别为m和n，那么于是乎，我们可以尝试划分两个序列，就会每个序列各自得到两个子集，将两个序列前部分子集合并、后部分子集合并，再判断当前切分得是否合理，如果合理，找到前一个合并子集的最大值、后一个合并子集的最小值，返回平均值（当m + n为偶数时），或直接返回前一个合并子集的最大值（当m + n为奇数时）。这样的思路里有两个地方需要进一步讨论：1. 如何划分子集？ 2. 如何判断划分得是否合理？接下来逐步讨论这

二分法 · 06-04

540. 有序数组中的单一元素

题目链接：https://leetcode.cn/problems/single-element-in-a-sorted-array/description/思路题目中要求了复杂度为$O(\log N)$，所以不能用线性扫描的方法，还是只能用二分法。其实刚拿到这题是没什么思路的，但看了一下题解的提示，知道了因为这个单独元素的插入，会破坏原始的元素重复的规律：在没有这个单独的元素前，始终是偶数位=奇数位，如此重复下去，比如[1,1,3,3,5,5]，其中每组两个重复元素11，33，55，对应的索引分别为01，23，45，都是左边为偶数索引，右边为奇数索引但是在插入了这个单独的元素后，这种规律被打破，比如[1,1,2,3,3,5,5]，这样一来，每组两个重复元素对应索引就变成了01，34，56，可以发现，在这个单独元素的左边，规律还是保持不变，左边为偶右边为奇，但在这个元素的右边，就变成了每组左边索引为奇，右边为偶可以利用这个规律来进行求解，梳理一下就是：假设mid落在单独元素的左边：如果mid为奇数，那么一定满足nums[mid] == nums[mid - 1]如果mid为偶数，那么一

默认分类 · 05-24

154. 寻找旋转排序数组中的最小值 II

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/我的思路基本上是延续153题的思路，但和153题不一样的是，这题中可能会有重复的相同元素出现，因此需要多加思考。考虑到的可能情况为：[3,3,1,3], [10,1,10,10,10]，nums[mid] >或< nums[r]的情况比较好解决，和153中的思路一样，但当二者相等时，要如何处理呢？一开始只想到了笨方法，有灵光一现想到只要考虑右边即可（因为原数组已经是按非递减顺序排好），但没有抓住这个思路继续想下去，而是继续尝试笨方法：分情况讨论。数值相同的情况可能有几种，比如[3,3,1,3]，l在0处，r在3处，mid = 1，以及[10,1,10,10,10]，l在0处，r在4处，mid = 2，那很自然想到说要判断一下mid前后的数值情况，如果nums[mid - 1] == nums[mid]，那就从左边缩短区间，l = mid + 1，如果nums[mid + 1] == nums[mid]，那

二分法 · 05-14

153. 寻找旋转排序数组中的最小值

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/我的思路经历了第34题的摧残后，这道题显得没有那么难了，拿到题目读了一下题意和要求后稍微调整了一下解法就顺利通过了，结果表现也还不错。但还是把这题记录下来，是其中有一个地方和34中不太一样，就是当nums[mid]<nums[r]时，应该将mid直接赋给r，而不是mid-1，解释：因为在这里我们要找到的时最小值，nums[mid]<nums[r]可能会存在于下面的情况：…18…3,1,2…9…，此时l位于18处，r位于9处，mid指向1，而1的前面是3，1就是我们要找的最小值了，因此不能把此时mid这个位置的元素给排除掉（我们之前mid-1就是因为从mid起，包括mid在内的右边部分全部没用了，所以才这么赋值），此时mid指向的位置就是r的最小值了，区间不能再从右边往里面缩了，之后的判断操作也只能从左边开始缩区间结果0ms 100%, 17.63MB 94.39%

二分法 · 05-08

34. 在排序数组中查找元素的第一个和最后一个位置

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/我的思路大前提：序列已经按非递减顺序排列好。题目要求时间复杂度只能为$O(\log n)$，因此不能用简单的指针法（那样的复杂度为n），只能用二分法来求解。用两次二分法，第一次找第一个出现的位置，第二次找最后一个出现的位置，二分法的时间复杂度本身就为$O(\log n)$，用两次加起来$O(\log n)+O(\log n)$也仍然是$O(\log n)$target出现位置肯定满足条件nums[mid] == target，但也需要进一步判断：第一次出现位置：mid == 0 or nums[mid - 1] < target （有可能回到了列表起点），如果都不符合，那说明nums[mid - 1] = target（这个时候不可能是>target了，否则和先决条件nums[mid] == target以及非递减序列的大前提矛盾），意味着此时的mid还不够靠左，要把mid

二分法 · 05-06

69. x的平方根 

题目链接：https://leetcode.cn/problems/sqrtx/description/我的思路明显的用二分法的问题，根据教材提示，已知输入为$x$，问题可转化为求$f(y)=y^2-x$的零点问题，可得$f(0)=0-x=-x<0, f(x)=x^2-x>0$，于是我们可以把初始区间定为$[0,x]$，然后开始二分。回顾一下二分的核心思想，不断缩短考察的区间，二分二分，顾名思义要取中间值$mid=(0+x)/2$，之后再判断$f(mid)$是大于0还是小于0，如果大于0，即$mid^2>x$，那就把区间设置为$[0,mid]$，如果小于0，即$mid^2<x$，那就把区间设置为$[mid,x]$，接着继续取新的二分中间值$mid_1=(l+r)/2$，这里的l和r分别代表了区间的左右边界值但是，卡在了这里，一开始只要找到了$mid^2<x$的值，就把mid作为结果返回，但后来发现这样不对，就不知道该怎么确定结果值了。这样的思路会让程序陷入死循环，或者直接返回更小的那个符合题意得值（比如x=6，二分会让程序跳到1，返回1，但应该是2），问题

二分法 · 05-03