|
|
堆 大根堆、小根堆
|
|
|
完全二叉树的概念只有最下面一层，最右边当节点为空
|
|
|
|
|
|
最大线段重合问题
|
|
|
给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间
|
|
|
规定：
|
|
|
1）线段的开始和结束位置一定都是整数值
|
|
|
2）线段重合区域的长度必须>=1
|
|
|
返回线段最多重合区域中，包含了几条线段？
|
|
|
|
|
|
1、将所有线段按照start升序排序
|
|
|
2、构造堆，保存当前重合所有重合线段的end, heap的size就是当前重合线段的数量
|
|
|
3、遍历所有线段，如果出现不重合线段则弹出不重合的线段，如果重合则加入end
|
|
|
|
|
|
手动改写堆（非常重要）！
|
|
|
系统提供的堆无法做到的事情：
|
|
|
1）已经入堆的元素，如果参与排序的指标方法变化，系统提供的堆无法做到时间复杂度O(logN)调整！都是O(N)的调整！
|
|
|
2）系统提供的堆只能弹出堆顶，做不到自由删除任何一个堆中的元素，或者说，无法在时间复杂度O(logN)内完成！一定会高于O(logN)
|
|
|
根本原因：无反向索引表
|
|
|
|
|
|
手动改写堆的代码讲解
|
|
|
1）建立反向索引表
|
|
|
2）建立比较器
|
|
|
3）核心在于各种结构相互配合，非常容易出错
|
|
|
|
|
|
给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op
|
|
|
两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
|
|
|
arr = [ 3 , 3 , 1 , 2, 1, 2, 5…
|
|
|
op = [ T , T, T, T, F, T, F…
|
|
|
依次表示：3用户购买了一件商品，3用户购买了一件商品，1用户购买了一件商品，2用户购买了一件商品，1用户退货了一件商品，2用户购买了一件商品，5用户退货了一件商品…
|
|
|
|
|
|
一对arr[i]和op[i]就代表一个事件：
|
|
|
用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品
|
|
|
op[i] == F就代表这个用户退货了一件商品
|
|
|
现在你作为电商平台负责人，你想在每一个事件到来的时候，
|
|
|
都给购买次数最多的前K名用户颁奖。
|
|
|
所以每个事件发生后，你都需要一个得奖名单（得奖区）。
|
|
|
|
|
|
得奖系统的规则：
|
|
|
1，如果某个用户购买商品数为0，但是又发生了退货事件，
|
|
|
则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户
|
|
|
2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
|
|
|
3，每次都是最多K个用户得奖，K也为传入的参数
|
|
|
如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
|
|
|
4，得奖系统分为得奖区和候选区，任何用户只要购买数>0，
|
|
|
一定在这两个区域中的一个
|
|
|
5，购买数最大的前K名用户进入得奖区，
|
|
|
在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区
|
|
|
6，如果购买数不足以进入得奖区的用户，进入候选区
|
|
|
7，如果候选区购买数最多的用户，已经足以进入得奖区，
|
|
|
该用户就会替换得奖区中购买数最少的用户（大于才能替换），
|
|
|
如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户
|
|
|
如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
|
|
|
8，候选区和得奖区是两套时间，
|
|
|
因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有
|
|
|
从得奖区出来进入候选区的用户，得奖区时间删除，
|
|
|
进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
|
|
|
从候选区出来进入得奖区的用户，候选区时间删除，
|
|
|
进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
|
|
|
9，如果某用户购买数==0，不管在哪个区域都离开，区域时间删除，
|
|
|
离开是指彻底离开，哪个区域也不会找到该用户
|
|
|
如果下次该用户又发生购买行为，产生>0的购买数，
|
|
|
会再次根据之前规则回到某个区域中，进入区域的时间重记
|
|
|
请遍历arr数组和op数组，遍历每一步输出一个得奖名单
|
|
|
|
|
|
public List<List<Integer>> topK (int[] arr, boolean[] op, int k)
|
