23. 合并K個(gè)升序鏈表
兩兩合并：
class Solution {
private ListNode merge(ListNode a, ListNode b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
if (a.val <= b.val) {
a.next = merge(a.next, b);
return a;
} else {
b.next = merge(a, b.next);
return b;
}
}
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = null;
for (ListNode node : lists) {
res = merge(res, node);
}
return res;
}
}
使用小根堆：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> q = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
for (ListNode node : lists) {
if (node != null) {
q.add(node);
}
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (!q.isEmpty()) {
ListNode front = q.poll();
cur.next = front;
cur = front;
if (front.next != null) {
q.offer(front.next);
}
}
return dummy.next;
}
}
215. 數(shù)組中的第K個(gè)最大元素
最經(jīng)典的面試問(wèn)題虫给，在實(shí)際生活中也應(yīng)用的非常廣泛廓旬。
創(chuàng)建容量最大為k的大根堆辛友，最后堆的最后一個(gè)元素就是topK。
class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> q = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
for (int i : nums) {
q.add(i);
}
for (int i = 0; i < k - 1; i++) {
q.poll();
}
return q.poll();
}
}
264. 丑數(shù) II
使用小根堆听怕，保證每次出隊(duì)的都是最小的。
class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[1690];
Set<Long> isVisit = new HashSet<>();
Queue<Long> heap = new PriorityQueue<>();
long curUgly, newUgly;
int[] primes = {2, 3, 5};
heap.offer(1L);
isVisit.add(1L);
for (int i = 0; i < 1690; i++) {
curUgly = heap.poll();
ugly[i] = (int) curUgly;
for (int j : primes) {
newUgly = curUgly * j;
if (!isVisit.contains(newUgly)) {
isVisit.add(newUgly);
heap.offer(newUgly);
}
}
}
return ugly[n - 1];
}
}
