共计 2548 个字符，预计需要花费 7 分钟才能阅读完成。
上次咱们聊了堆和堆排序，这次咱们就顺着说说和堆无关的题目。
一、简直有序的数组排序
1、题目形容
已知一个简直有序的数组，简直有序是指，如果把数组排好序的话，每个元素挪动的间隔肯定不超过 K，并且 K 绝对于数组长度来说是比拟小的。
请抉择一个适合的排序策略，对这个数组进行排序。
2、解决思路：
从第一个数开始，
将 前K+ 1 个数放到小根堆里，弹出第一个数放到数组第一个地位；
将 第K+ 2 个数放到这个小根堆里，再弹出第一个数放到数组第二个地位；
将 第K+ 3 个数放到这个小根堆里，再弹出第一个数放到数组第三个地位；
直到小根堆为空
3、具体的参考代码：
/**
* @author Java 和算法学习：周一
*/
public static void sortArrayDistanceLessK(int[] arr, int k) {if (arr == null || arr.length < 2 || k == 0) {return;}
// 默认是小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
// 标记以后曾经放到堆中元素的数组下标
int index = 0;
// 将前 k 个数放进数组中
for (; index < k; index++) {heap.add(arr[index]);
}
// 标记以后数组中曾经排好序的下标
int i = 0;
// 从第 k + 1 个数始终到数组最初一个数，for (; index < arr.length; index++) {
// 每次放进堆中一个数，heap.add(arr[index]);
// 同时弹出此时堆顶元素放到数组中，排序下标后移
arr[i++] = heap.poll();}
// 将小根堆中残余数据放到数组中
while (!heap.isEmpty()) {arr[i++] = heap.poll();}
}
4、工夫复杂度为 O(N*logK)
堆中只有 K + 1 个数，也就是调整为小根堆的过程，工夫复杂度是 logK，因为须要遍历一遍整个数组，所以最初的工夫复杂度是 O(N*logK)。
二、最大线段重合问题
1、题目形容
给定很多线段，每个线段都有两个数[start, end]，示意线段开始地位和完结地位，左右都是闭区间。
规定：
1）线段的开始地位和完结地位肯定都是整数
2）两个线段重合的定义：线段重合区域的长度必须 >= 1 才示意线段重合
求：线段最多的重合区域中，蕴含了几条线段。
2、解决思路
1）将所有线段依照开始地位从小到大排序，同时筹备一个小根堆用于寄存线段完结地位
2）遍历排序后的所有线段，将此时小根堆里小于等于此时线段开始地位的数弹出，同时将此时线段完结地位的数放到小根堆里，此时小根堆的个数即是从此时线段开始地位作为重合区域左边界的重合区域所蕴含线段的个数。（任何重合区域的左边界必然是某个线段的左边界）
因为此时小根堆里的数示意之前线段的右边界会穿过此时线段的左边界，而之前线段的左边界是小于此时线段的左边界的，所以小根堆的个数即是重合区域中蕴含线段的个数。
3）最初第 2 步中 最大的个数 即是 蕴含线段最多的重合区域中所蕴含的线段数
3、具体的参考代码：
/**
* @author Java 和算法学习：周一
*/
public static class Line {
private int start;
private int end;
public Line(int start, int end) {
this.start = start;
this.end = end;
}
}
/**
* 工夫复杂度 O(N*logN)
*/
public static int lineCoverMaxByHeap(int[][] n) {Line[] lines = new Line[n.length];
for (int i = 0; i < n.length; i++) {lines[i] = new Line(n[i][0], n[i][1]);
}
// 将所有线段依照开始下标从小到大排序
Arrays.sort(lines, (o1, o2) -> o1.start - o2.start);
// 筹备一个小根堆（寄存线段的完结值）PriorityQueue<Integer> heap = new PriorityQueue<>();
int cover = 0;
for (Line line : lines) {// O(N)
// 将小根堆中所有小于等于以后线段开始值的数据弹出
while (!heap.isEmpty() && heap.peek() <= line.start) {// O(logN)
heap.poll();}
// 将以后线段的完结值放到小根堆中
heap.add(line.end);
cover = Math.max(cover, heap.size());
}
return cover;
}
蕴含测试的所有代码 Github 获取
