合并k个升序链表
题目描述
解答思路
这个题目可用暴力解法，遍历收集所有链表结点，然后进行排序，再将排序后的结点串联为一个链表。时间复杂度方面，遍历所有结点和将所有结点串联为一个链表的时间复杂度为O（n），排序最优的时间复杂度为O（nlogn），因此总时间复杂度为O（nlogn）。由于需要容器收集所有结点，因此空间复杂度为O（n）。
另一种解法，使用堆结构，我们将链表数组的所有头结点加入到小根堆中，每次弹出堆顶结点，并将该结点的下一个结点加入到链表中，依次将弹出的结点串联起来，就得到了一个升序链表。
public ListNode mergeKLists(ListNode[] lists) {
// 小根堆
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for(ListNode h:lists){
if(h!=null) heap.add(h);
}
// 如果所有链表都为空，返回null
if(heap.isEmpty()) return null;
// 先弹出一个结点作为最终链表的头结点
// 将其下一个结点加入堆中
ListNode head=heap.poll();
if(head.next!=null) heap.add(head.next);
ListNode pre=head;
while(!heap.isEmpty()){
ListNode cur=heap.poll();
pre.next=cur;
pre=pre.next;
if(cur.next!=null) heap.add(cur.next);
}
return head;
}
该方法时间复杂度为O（n*logk），其中k为小根堆的大小，也即链表数组中，链表的个数，空间复杂度为O（k）。
线段重合问题
题目描述
如图，在[1,2]位置和[2,3]位置都重合了两条线段，因此在同一位置最多重合2条线段。
解答思路
首先明确一个结论，任何一个重合区域的左边界一定都是某条线段的左边界。我们首先将线段的起点按从小到大排序，然后每次将线段的终点加入到小根堆中，在加入之前，要先让小根堆中小于等于该线段起点的值弹出，此时小根堆中元素的数量就是此时可重合的线段数量。由于小于等于该起点的值被弹出，意味着该值不会与后面的线段有所重合了，而剩下的就是当前加入该线段后重合的线段数量。
public static int MAXN = 10001;
public static int[][] line = new int[MAXN][2];
public static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
for (int i = 0; i < n; i++) {
in.nextToken();
line[i][0] = (int) in.nval;
in.nextToken();
line[i][1] = (int) in.nval;
}
out.println(compute());
}
out.flush();
out.close();
br.close();
}
public static int compute() {
// 堆的清空
size = 0;
// 线段一共有n条，line[0...n-1][2] : line[i][0] line[i][1], 左闭右闭
// 所有线段，根据开始位置排序，结束位置无所谓
// 比较器的用法
// line [0...n) 排序 : 所有小数组，开始位置谁小谁在前
Arrays.sort(line, 0, n, (a, b) -> a[0] - b[0]);
int ans = 0;
for (int i = 0; i < n; i++) {
// i : line[i][0] line[i][1]
while (size > 0 && heap[0] <= line[i][0]) {
pop();
}
add(line[i][1]);
ans = Math.max(ans, size);
}
return ans;
}
// 小根堆，堆顶0位置
public static int[] heap = new int[MAXN];
// 堆的大小
public static int size;
// 加入新元素，并重新调整堆结构
public static void add(int x) {
heap[size] = x;
int i = size++;
while (heap[i] < heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
// 弹出堆顶元素，并重新调整堆结构
public static void pop() {
swap(0, --size);
int i = 0, l = 1;
while (l < size) {
int best = l + 1 < size && heap[l + 1] < heap[l] ? l + 1 : l;
best = heap[best] < heap[i] ? best : i;
if (best == i) {
break;
}
swap(i, best);
i = best;
l = i * 2 + 1;
}
}
public static void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
有n条线段，因此有n个结束位置，每个结束位置只会进入堆一次，堆调整的时间复杂度为O（logn），因此总时间复杂度为O（n*logn），空间复杂度为O（n）。
将数组和减半的最小操作次数
题目描述
解题思路
贪心思想，既然要求将数组和至少减少一半的最少操作次数，那么每次将数组中的最大数减小一半，一定是操作次数最少的。我们可以采用大根堆实现，每次将堆顶元素减半，再将减半后的元素入堆，最终，直到总共减小的幅度大于等于数组和的一半，操作次数即为所求。
public static int halveArray(int[] nums) {
// 大根堆
PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
double sum = 0;
for (int num : nums) {
heap.add((double) num);
sum += num;
}
// sum，整体累加和，-> 要减少的目标！
sum /= 2;
int ans = 0;
for (double minus = 0, cur; minus < sum; ans++, minus += cur) {
cur = heap.poll() / 2;
heap.add(cur);
}
return ans;
}
时间复杂度分析：如果遍历数组，将数组中每个元素都减半，一定可以使数组和减半，而每次将最大数减半，这样操作的次数一定比每个元素都减半的操作次数少，而再加上堆的操作，时间复杂度为O（n*logn）。
空间复杂度O（n）。
如果还想要进一步优化，可以自己实现大根堆。此外，本题中的数据是要求保留小数的，因此用的是double类型，但double类型也有精度限制，因此可能出现一定问题，这里左神提到了一个方法，我们将每个元素都扩大220倍，数组和也变为原来的220，在此情况下求解该问题，与原本情况下求解的答案不变。因为int类型数据占32位，就算扩大220倍，也不会超过long的表示范围，此时就相当于把int型数据的位数进行了扩展，也即精度增大了，避免求解时的精度错误。
