7.加强堆与堆相关题目分析 总览笔记思维导图链接常见题目汇总:
题目描述:题解:代码实现:复杂度分析:
7.加强堆与堆相关题目分析 总览 笔记思维导图链接算法与数据结构思维导图
常见题目汇总: 题1:最大线段重合问题(堆实现) 题目描述:参考左程云算法课程
给定很多线段,每个线段都有两个数组[start, end],
表示线段开始位置和结束位置,左右都是闭区间
规定:
1)线段的开始和结束位置一定都是整数值
2)线段重合区域的长度必须>=1
返回线段最多重合区域中,包含了几条线段
题解: 代码实现:package class07; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class Code01_CoverMax { // 创建line线段类对象,将二维数组对象转为线段对象,方便处理arr[a,b]->line(a,b) public static class Line { private int start; private int end; public Line(int start, int end) { super(); this.start = start; this.end = end; } } // 方法1:暴力统计算法 public static int maxCover1(int[][] lines) { // 1. 确定线段最小和最大范围,锁定要校验的对象 int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int i = 0; i < lines.length; i++) { min = Math.min(min, lines[i][0]); max = Math.max(max, lines[i][1]); } // 2. 以每个在范围内的数的.5为基点,遍历统计包含该数的所有线段数 int cover = 0; for (double p = min + 0.5; p < max; p += 1) { int cur = 0; for (int i = 0; i < lines.length; i++) { if (lines[i][0] < p && lines[i][1] > p) { cur++; } } cover = Math.max(cover, cur); } return cover; } // 方法2:使用最小堆结构 public static int maxCover2(int[][] m) { // 1. 将线段按照左边界大小进行排序 // 先将二维数组转为线段对象,方便比较排序处理 // 将各二维数组new出线段对象放在一个一维的线段类型数组中 Line[] lines = new Line[m.length]; for (int i = 0; i < lines.length; i++) { lines[i] = new Line(m[i][0], m[i][1]); } Arrays.sort(lines, (a, b) -> a.start - b.start); // 2. 依次遍历所有左边界,并维护最小堆 PriorityQueue复杂度分析:minHeap = new PriorityQueue<>(); int res = 0; for (int i = 0; i < lines.length; i++) { // 弹入前,先判断弹出不满足的线段 // 注意,等于也弹出,等于,说明线段相连,重合部分为0 while (!minHeap.isEmpty() && lines[i].start >= minHeap.peek()) minHeap.poll(); // d干净后,再d入右边界值 minHeap.add(lines[i].end); // 3. 统计每个基点的重合线段数,并比较出最大值 res = Math.max(res, minHeap.size()); } return res; } // for test public static int[][] generateLines(int N, int L, int R) { int size = (int) (Math.random() * N) + 1; int[][] ans = new int[size][2]; for (int i = 0; i < size; i++) { int a = L + (int) (Math.random() * (R - L + 1)); int b = L + (int) (Math.random() * (R - L + 1)); if (a == b) { b = a + 1; } ans[i][0] = Math.min(a, b); ans[i][1] = Math.max(a, b); } return ans; } public static class StartComparator implements Comparator { @Override public int compare(Line o1, Line o2) { return o1.start - o2.start; } } public static void main(String[] args) { Line l1 = new Line(4, 9); Line l2 = new Line(1, 4); Line l3 = new Line(7, 15); Line l4 = new Line(2, 4); Line l5 = new Line(4, 6); Line l6 = new Line(3, 7); // 底层堆结构,heap PriorityQueue heap = new PriorityQueue<>(new StartComparator()); heap.add(l1); heap.add(l2); heap.add(l3); heap.add(l4); heap.add(l5); heap.add(l6); while (!heap.isEmpty()) { Line cur = heap.poll(); System.out.println(cur.start + "," + cur.end); } System.out.println("test begin"); int N = 100; int L = 0; int R = 200; int testTimes = 200000; for (int i = 0; i < testTimes; i++) { int[][] lines = generateLines(N, L, R); int ans1 = maxCover1(lines); int ans2 = maxCover2(lines); if (ans1 != ans2) { System.out.println("Oops!"); } } System.out.println("test end"); } }
1.线段排序为O(NlogN)
2.循环遍历左边界,并维护最小堆,统计比较O(NlogN):
for循环: 所有线段考察一次O(N)
小根堆复杂度: 所有线段结尾位置, 最多进一次, 最多出一次, 一共进出2N
小根堆每次调整代价logN(shiftUP,shiftDownd堆化都是logn)
总复杂度O(N*logN)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)