在面试过程中，一些手撕代码的高频问题值得总结和记录。如：Top K 问题的多种解法、一道结合「简单数据结构 & 简单算法」的面试题、既能考察对「数据结构」的掌握，还能考察对「递归函数」的设计、
文章目录- 一、Top K 问题的多种解法
- 703. 数据流中的第 K 大元素
- 1. 冒泡排序法
- 2. 快速排序法
- 3. 优先队列法
- 二、一道结合「简单数据结构 & 简单算法」的面试题
- 21. 合并两个有序链表
- 1. 双指针解法（哨兵技巧）
- 2. 递归法实现
- 三、既能考察对「数据结构」的掌握，还能考察对「递归函数」的设计
- 24. 两两交换链表中的节点
- 1. 递归解法
- 2. 迭代解法（哨兵技巧）
leetcode题目链接：703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
- KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
- int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例一：
输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8] 解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
提示：
- 1 <= k <= 104
- 0 <= nums.length <= 104
- -104 <= nums[i] <= 104
- -104 <= val <= 104
- 最多调用 add 方法 104 次
- 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素
每次调用 add 时先将数装入数组，然后遍历 k 次，通过找 k 次最大值来找到 Top K。
但冒泡排序会导致超时。
class KthLargest {
// 冒泡排序
int k;
List list = new ArrayList<>(10009);
public KthLargest(int k, int[] nums) {
this.k = k;
for (int i : nums) {
list.add(i);
}
}
public int add(int val) { // 冒泡排序
list.add(val);
int cur = 0;
for (int i = 0; i < k; i++) { // 遍历k次，通过找k次最大值找到Top K
int idx = findMax(cur, list.size() - 1);
swap(cur++, idx);
}
return list.get(cur - 1);
}
int findMax(int start, int end) {
int ans = 0, max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
int t = list.get(i);
if (t > max) {
max = t;
ans = i;
}
}
return ans;
}
void swap(int a, int b) {
int c = list.get(a);
list.set(a, list.get(b));
list.set(b, c);
}
}
2. 快速排序法
上述的解法时间复杂度是 O(nk) 的，当 k 很大的时候会超时。
我们可以使用快排来代替冒泡。
class KthLargest {
// 快排
int k;
List list = new ArrayList<>(10009);
public KthLargest(int k, int[] nums) {
this.k = k;
for (int i : nums) {
list.add(i);
}
}
public int add(int val) {
list.add(val);
Collections.sort(list);
return list.get(list.size() - k);
}
}
Collections.sort 内部最终会调用 Arrays.sort 进行排序。而 Arrays.sort() 本身不只有「双轴快排」一种实现，在排序数量少的情况下会直接使用「冒泡排序」，这里的分析是假定了 Collections.sort 最终使用的是 Arrays.sort 的「双轴快排」。
3. 优先队列法使用优先队列构建一个容量为 k 的小根堆。
将 nums 中的前 k 项放入优先队列（此时堆顶元素为前 k 项的最大值）。
随后逐项加入优先队列：
- 堆内元素个数达到 k 个：
- 加入项小于等于堆顶元素：加入项排在第 k 大元素的后面。直接忽略
- 加入项大于堆顶元素：将堆顶元素弹出，加入项加入优先队列，调整堆
- 堆内元素个数不足 k 个，将加入项加入优先队列
将堆顶元素进行返回（数据保证返回答案时，堆内必然有 k 个元素）。
class KthLargest {
// 优先队列
int k;
PriorityQueue queue;
public KthLargest(int k, int[] nums) {
this.k = k;
queue = new PriorityQueue<>(k, (a,b)->Integer.compare(a,b)); // 小根堆
for (int i = 0; i < nums.length && i < k; i++) {
queue.add(nums[i]);
}
for (int i = k; i < nums.length; i++) {
add(nums[i]);
}
}
public int add(int val) {
int t = !queue.isEmpty() ? queue.peek() : Integer.MIN_VALUE;
if (val > t || queue.size() < k) { // 加入项大于堆顶元素，将堆顶元素弹出
if (!queue.isEmpty() && queue.size() >= k) {
queue.poll();
}
queue.add(val); // 加入项加入优先队列，调整堆
}
return queue.peek(); // 堆顶元素就是第K大元素
}
}
1. 为什么使用小根堆？
- 因为我们需要在堆中保留数据流中的前 K 大元素，使用小根堆能保证每次调用堆的 pop()函数时，从堆中删除的是堆中的最小的元素（堆顶）。
2. 为什么能保证堆顶元素是第 K 大元素？
- 因为小根堆中保留的一直是堆中的前 K 大的元素，堆的大小是 K，所以堆顶元素是第 K 大元素。
3. 每次 add() 的时间复杂度是多少？
- 每次 add() 时，调用了堆的 push() 和 pop() 方法，两个操作的时间复杂度都是 log(K).
参考：
面试题警告：经典 TopK ，本题需要重点学习
【面试高频系列】Top K 问题的多种解法：冒泡排序 & 快速排序 & 优先队列
二、一道结合「简单数据结构 & 简单算法」的面试题 21. 合并两个有序链表leetcode题目链接：21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]1. 双指针解法（哨兵技巧）
做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。
由于两条链表本身就是有序的，只需要在遍历过程中进行比较即可：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 1. 双指针,类似于归并排序中的合并过程
// 虚拟头节点
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
cur = cur.next;
list1 = list1.next;
} else {
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if (list1 == null) cur.next = list2;
if (list2 == null) cur.next = list1;
return dummy.next;
}
}
2. 递归法实现
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 递归
if (list1 == null) {
return list2;
}
else if (list2 == null) {
return list1;
}
else if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：我们判断 list1 和 list2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
参考：
一看就会，一写就废？详解递归
【面试高频系列】一道结合「简单数据结构 & 简单算法」的面试题
三、既能考察对「数据结构」的掌握，还能考察对「递归函数」的设计 24. 两两交换链表中的节点leetcode题目链接：24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例一：
输入：head = [1,2,3,4] 输出：[2,1,4,3]1. 递归解法
链表和树的题目天然适合使用递归来做。
我们可以设计一个递归函数，接受一个 ListNode 节点 root 作为参数，函数的作用是将 root 后面的两个节点进行交换，交换完成后再将下一个节点传入 …
交换的前提条件：节点 root 后面至少有两个节点。
class Solution {
public ListNode swapPairs(ListNode head) {
// 递归
if(head == null || head.next == null) return head;
ListNode next = head.next;
ListNode newNode = swapPairs(next.next);
next.next = head;
head.next = newNode;
return next;
}
}
2. 迭代解法（哨兵技巧）
做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。
class Solution {
public ListNode swapPairs(ListNode head) {
// 设置虚拟头节点，交换相邻两个元素
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tmp = dummy;
while(tmp.next != null && tmp.next.next != null) {
ListNode node1 = tmp.next;
ListNode node2 = tmp.next.next;
tmp.next = node2;
node1.next = node2.next;
node2.next = node1;
tmp = node1;
}
return dummy.next;
}
}
参考：
【面试高频系列】既能考察对「数据结构」的掌握，还能考察对「递归函数」的设计
