前缀和
- 某一区间上的累加和：sum[i……j]=arr[0……j]-arr[0……i-1]
- 前缀和不一定是单调递增的，因为有负数存在
- 前缀和不是有序的！！！
- 有用有序表的必要
子数组的和在某一范围之内
- 采用暴力为O(N3)
- 加上前缀和为O(N2)
- 转换的思想：将两端都不固定的区间化为一端固定
- 对前缀和数组处理，不用原来的数组了（只看前缀和）
- merge干了什么：求左组关于右组有几个是达标的或者右组关于左组有几个是达标的
- 本质上为在merge方法中变化（并且合并的过程中只要一边对另一边即可，不必两边重复算）
- 不回退O(N)
- 不回退才行；虽然是for中套while，但是因为while是不回退的，所以依然是O(N)
- 计算和merge分开！！！
- 为什么感觉左边的没求，因为这是递归，实际上是求过的，并且虽然在merge的时候会改变顺序，但是这个顺序已经使用过了，这时应该只要看右边对于左边有几种情况即可！
- 窗口表示法是左闭右开！可以不用和0比大小
- 窗口表示法也可以左闭右闭但一般不用
- 左闭右开常用
- windowL取得是左边满足条件的第一个位置，用的是<
- windowR取得是右边满足条件的最后一个位置的后一个位置，用的是<=
- 使用归并排序时，左边右边一定是分别有序的，而恰好前缀和数组也是有序的
- 运用前缀和，将原来的[lower, upper]转换为前缀和数组中求新指标的问题
- merge过程必须做到左组和右组做到是O(N)的，不回退的技巧（必须为O(N)，因为合并的复杂度也为O(N)，不能超过这个大小）
- 这一题的重点不在于排序，而在于运用合并或者（排序的目的在于使数组变得有序方便求范围！）
- 在求范围上能够很大程度地减小复杂度
- 归并解题的技巧！
- 二分、多分的思想
- 前缀和并不是有序的，因为会有负数的出现！比如221，-221，123，232……
- 其他解法：用有序表来解，比归并排序少绕弯路，更好理解
- 将前缀和塞到有序表中去
- 去找有序表中有多少数是在[100-upper, 100-lower]范围中的（有序表结构可以直接找出这样的数就行了，系统的有序表没有这个结构，所以要自己搞清楚有序表，自己实现）
- 简单排序不光要会、要理解，还要会改写他！
先别管边界，先把框架写好，再去慢慢处理边界
荷兰国旗问题
双轴快排（三轴快排？）
快排1.0（非学术概念上的快排）
- 荷兰国旗中间那个数已经排好了
- 之后看左边和右边
- 每次搞定一个数
快排2.0（非学术概念上的快排）
- 每次搞定一批数
- 用范围最右侧的值做划分值
快排3.0===>随机快排（学术概念上的快排）
- 1.0和2.0都是O(N2)===>最坏情况[1,2,3,4,5,6,7]
- 多个 随机选择一个数换到右边去，做划分值
- 有什么好处：
- 避免划分值打偏了，不是在中间的值，而是在边上的值（为什么2.0效果差）
- 打得越偏，效果越差，复杂度越高
- 打得很正的时候就是master公式（等规模递归）
- 打得好向O(N*logN)收敛，打得不好向O(N2)收敛
- 快排没有稳定性这个概念（稳定性的概念：不是复杂度忽高忽低）
- 等概率选随机数，最坏情况和最好情况都不是必命中的，是概率事件，权重机会是1/N
- 复杂度要求所有情况的概率叠加，最终能证明收敛到O(N*logN)===>期望（概率论与数理统计）
- 快排的额外空间复杂度O(logN)
- 不用递归做，一定要记住中间的划分点信息，一个划分值要处于中间位置，左侧递归完后回到这一层去做右侧递归时要用到右侧的范围
- 递归===>迭代
- 递归是系统帮你记下来，迭代是自己维护！
- 最差情况下额外空间：O(N)，每一个点都要去记[1,2,3,4,5,6,7]
- 最好情况即中间位置：左侧四个变量，到右侧时将之前的左侧的释放了去记右侧的划分点值
- 是一个二叉树===>释放复用，所以额外空间复杂度为O(logN)
- 介于最好、最坏之间：都是1/N的概率，长期的概率期望，额外空间复杂度收敛到O(logN)
- 用栈替换了递归调用（不能不用栈，因为中点位置一定要记，不用栈只用几个有限的变量可以发论文得奖图灵奖）
- 递归到非递归实质就是用自己的栈替代系统栈
- 递归和非递归的复杂度没有区别（只是实现方式不同）
- 递归也是概率期望
若有收获，就点个赞吧
0 人点赞
