时间：2020/4/12 Topic : 堆题目 复杂度格式: 时间复杂度, 空间复杂度
- 方法：队列直接应用
- 大顶堆：每个结点的值都大于或等于其左右孩子结点的值；
- 小顶堆：每个结点的值都小于或等于其左右孩子结点的值；
1.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
- 时间复杂度：O(n+nlogn)
- 空间复杂度：O(1)
- 考虑到 需要找到 第 k 大 的 数，所以可以将前 k 大 的数 都保存到 一个 数组中
- 定义 一个 长度为 k+1 的数组 res_list，用于保存前 k+1 个 数；
- 遍历数组，然后比较当前元素 num 和 res_list 中 元素 间的大小（从后到前比较）：
- 若 大于，则将 res_list 后移，然后插入 num
时间复杂度：$O(n*(k+1))$
空间复杂度：$O(k+1)$
- 利用堆 每一次 都能 找到 当前 最大的数，所以只要 进行 k 次 堆排序 即可找到 第 k 大 的数
- 编写堆排序算法；
- 进行 k 次 堆排序；
时间复杂度：$O(n*nlogK)$
空间复杂度：$O(1)$
- 对 数组进行快排，然后 取位置 k 元素 即可；
时间复杂度：$O(nlogn)$
空间复杂度：$O(1)$
- 建立大小为k的最大堆，时间O(k)；
-
- 遍历每一个元素，如果比堆顶小则加入堆，最后返回堆顶元素即为第k小元素。时间O(n^2logk)；
时间复杂度：O( k + n^2logk)
空间复杂度O(k)
- 首先将二维数组合并成对应的一维数组
- 然后对这个一维数组排序，今天我使用的快速排序
- 最后返回第k-1个元素即可
时间复杂度：$O(n^2logn)$
空间复杂度：$O(n^2)$
- 找出二维矩阵中最小的数left，最大的数right，那么第k小的数必定在left~right之间
- mid=(left+right) / 2；在二维矩阵中寻找小于等于mid的元素个数count
- 若这个count小于k，表明第k小的数在右半部分且不包含mid，即left=mid+1, right=right，又保证了第k小的数在left~right之间
- 若这个count大于k，表明第k小的数在左半部分且可能包含mid，即left=left, right=mid，又保证了第k小的数在left~right之间
- 因为每次循环中都保证了第k小的数在left~right之间，当left==right时，第k小的数即被找出，等于right
时间复杂度：$O(n^2logn)$
空间复杂度：$O(n^2)$
- 因为每一行都是有序的，所以每一行的最小值（最左边）中最小一个必定是矩阵的最小值。。
- 取出这个最小值（即整个矩阵的最小值），同时使用这一行的下一个元素参与下一次比较。
- 循环上述步骤直到取到第k个最小值。
时间复杂度：$O(min(k,N)) + k*O(log(min(k,N)))$
空间复杂度：$O(min(k,N))$
- 建立一个大顶堆(小的那一半)一个小顶堆(大的那一半元素)，堆顶保存着数组的中间两个数。
- 插入的时候：
- 若两个堆长度一样，则插入新元素，会先加到大顶堆，再把大堆顶元素加到小顶堆；
- 若第一个堆长度大于第二个，则插入新元素，会先加到小顶堆，再把小堆顶元素加到大顶堆；
- 查询时：
- 若两个堆长度一样， 取两个堆顶平均；
- 若第一个堆长度大于第二个，小顶堆堆顶元素
时间复杂度：O(logn)
空间复杂度：$O(n)$
一种针对本体比较合适而且简单的解法，使用二分插入，python自带的bisect,初始化一个数组，当数组为空时直接append，如果不为空，则使用bisect.insort_left，按顺序插入元素，这样每一步过后数组都是有序的，每一步加入元素只是需要二分查找插入位置
时间复杂度O(lgn) + O(n)
空间复杂度O(n)