1 比较器
//返回负数的情况，就是o1比o2优先的情况//返回正数的情况，就是o2比o1优先的情况//返回0的情况，就是o1与o2同样优先的情况public class Code01_MyComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}}
实现比较器，可以应用在特殊的排序上，也可以应用在根据特殊标准排序的结构上（如LinkedHashMap
2 堆结构
1）堆结构就是用数组实现的完全二叉树结构（完全二叉树：每一层节点都是满的，就算不满也是从左到右变满的过程）
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert（向上调整）与heapify（向下调整）操作
5）堆结构的增大和减少 （有heapSize）进行控制
6）优先级队列结构（PrioritQueue
//大根堆class MaxHeap {private int[] heap;private int size;private static final int DEFAULT_INITIAL_LENGTH = 16;private int limit;public MaxHeap() {heap = new int[DEFAULT_INITIAL_LENGTH];limit = DEFAULT_INITIAL_LENGTH;size = 0;}public MaxHeap(int limit) {heap = new int[limit];this.limit = limit;size = 0;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == limit;}public void push(int value) throws RuntimeException {if (size < limit) {heap[size] = value;heapInsert(heap, size++);} else {throw new RuntimeException("index out of bounds");}}public int pop() {if (size == 0) {throw new RuntimeException("heap is null");}int ans = heap[0];swap(heap, 0, --size);heapify(heap, 0, size);return ans;}public int peek() {if (size == 0) {throw new RuntimeException("heap is null");}return heap[0];}//向上调整private void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}//向下调整private void heapify(int[] arr, int index, int heapSize) {while ((2 * index + 1) < heapSize) {int large = 2 * index + 2 < heapSize && arr[2 * index + 2] > arr[2 * index + 1] ? (2 * index + 2) : (2 * index + 1);large = arr[large] > arr[index] ? large : index;if (large == index) {break;}swap(arr, index, large);index = large;}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}@Overridepublic String toString() {return "MyHeap{" +"heap=" + Arrays.toString(heap) +'}';}}
题目1 堆排序
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//将数组调整为大根堆
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapSize = arr.length;
while (heapSize > 0) {
swap(arr, 0, --heapSize);
heapify(arr, 0, heapSize);
}
}
private static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private static void heapify(int[] arr, int index, int heapSize) {
while ((2 * index + 1) < heapSize) {
int large = ((2 * index + 2) < heapSize) && (arr[2 * index + 2] > arr[2 * index + 1]) ? (2 * index + 2) : (2 * index + 1);
large = arr[large] > arr[index] ? large : index;
if (large == index) {
break;
}
swap(arr, large, index);
index = large;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//将数组调整为大根堆 写法1（一个数一个数的给数组数） 时间复杂度O(N*logN)
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
//将数组调整为大根堆 写法2（一次性给数组全部数） 时间复杂度O(N)
int heapSize = arr.length;
for (int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, heapSize);
}
题目2 几乎有序数组排序
已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序。
public static void sortArrLessDistanceK(int[] arr, int k) {
if (k == 0) {
return;
}
//PriorityQueue为小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
//0-k-1放入小根堆
for (; index <= Math.min(k - 1, arr.length - 1); index++) {
heap.add(arr[index]);
}
int i = 0;
for (; index < arr.length; index++, i++) {
heap.add(arr[index]);
arr[i] = heap.poll();
}
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
题目3 最大线段重合问题（用堆的实现）
给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间
规定：1）线段的开始和结束位置一定都是整数值，2）线段重合区域的长度必须>=1；
返回线段最多重合区域中，包含了几条线段
public static int coverMax(int[][] lines) {
if (lines == null || lines.length < 1) {
return 0;
}
Arrays.sort(lines, Comparator.comparingInt(e -> e[0]));
PriorityQueue<Integer> heap = new PriorityQueue<>(lines.length);
int ans = 0;
for (int i = 0; i < lines.length; i++) {
while (!heap.isEmpty() && heap.peek() <= lines[i][0]) {
heap.poll();
}
heap.add(lines[i][1]);
ans = Math.max(ans, heap.size());
}
return ans;
}
/*以下为比较器，用于测试*/
public static int comparator(int[][] lines) {
if (lines == null || lines.length < 1) {
return 0;
}
int minStart = lines[0][0];
int maxEnd = lines[0][1];
for (int i = 1; i < lines.length; i++) {
minStart = Math.min(minStart, lines[i][0]);
maxEnd = Math.max(maxEnd, lines[i][1]);
}
int[] count = new int[maxEnd - minStart];
double newIndex = minStart + 0.5;
for (int i = 0; i < count.length; i++) {
for (int j = 0; j < lines.length; j++) {
if (newIndex > lines[j][0] && newIndex < lines[j][1]) {
count[i]++;
}
}
newIndex++;
}
int ans = count[0];
for (int i = 1; i < count.length; i++) {
ans = Math.max(ans, count[i]);
}
return ans;
}
public static int[][] generateLines(int maxNum, int minStart, int maxEnd) {
int[][] lines = new int[(int) (Math.random() * maxNum) + 1][2];
for (int i = 0; i < lines.length; i++) {
lines[i][0] = minStart + (int) (Math.random() * (maxEnd - minStart + 1));
lines[i][1] = lines[i][0] + (int) (Math.random() * (maxEnd - minStart + 1) + 1);
}
return lines;
}
若有收获，就点个赞吧
0 人点赞
