1.Talk is cheap, show you my code.
Please pay attention to the remark.
package solutions.algorithms.interview.merge;
import java.util.Arrays;
/**
* 算法上下文：DC 、 DFS 、 BFS 、 DP 、 GD
* 语法分析三工具：状态机、文法、函数
* LeetCode三连
* 其中前三是字节三轮面试的算法题
* 中间两道也是某头部第一三轮面试的算法题
* 最后一道是阿里一面的算法（不跑测试用例，说思路）
* 均与分而治之相关
*/
public class MergeSolution {
/**
* 面试时是会可能让你手写测试用例，因此前期刷题根基不稳的情况可以考虑取巧，手写必然使你的代码输出结果符合预期的测试用例。
* @param strings
*/
public static void main(String[] strings) {
//测试1：有序二路归并
int[] num1 = {1, 3, 5, 0, 0};
int[] num2 = {2, 4, 6};
mergeTwoArrays(num1, num2, 3, 2);
System.out.println(Arrays.toString(num1));
//测试2：链表归并排序
ListNode node = new ListNode(3);
ListNode head = node;
node = node.next = new ListNode(5);
node = node.next = new ListNode(2);
node = node.next = new ListNode(4);
node = node.next = new ListNode(-3);
node = node.next = new ListNode(-133);
node = node.next = new ListNode(13);
System.out.println(mergeSortLinkedList(head));
num2 = new int[]{4,89,1,13,4,6};
quickSort(num2, 0, num2.length - 1);
System.out.println(Arrays.toString(num2));
//测试3：多路归并
int[][] ints = {
{1, 3, 5, 7, 9},
{2, 4, 6, 8, 10},
{11, 14, 16, 17, 19}
};
//测试3.1：降维+分治法
// System.out.println(Arrays.toString(mergeSort(ints, 0, ints.length - 1)));
//测试3.2：败者树归并
System.out.println(Arrays.toString(mergeSortByLoseTree(ints)));
int[] arr1 = {1, 3, 5, 7, 9};
int[] arr2 = {2, 4, 6, 8, 10};
//测试4：有序二路第K大数
System.out.println(kthMergeArrays(arr1, arr2, 7));
//测试5：有序二路中位数
System.out.println(middleVals(arr1, arr2));
//测试6：快速排序
int[] arrays = {4, 6, 7, 12, 5, 3, 2, 1, 7};
quickSort(arrays, 0, arrays.length - 1);
System.out.println(Arrays.toString(arrays));
}
/**
* 一个正序数组num1的有效元素长度为m,总长度为(m + n)，
* 另一个正序数组num2的有效元素长度为n,总长度为n，
* 在num1上合并两个数组。
* 归并两个有序数组
* 1.常规做法：
* 构造一个新的大数组，用两指针分别指向两个子数组通过比较合并元素到新数组（二路归并思路），最后把大数组复制回数组1即可;
* 时间复杂度：O（n + m）
* 空间复杂度：O（n + m）
* 2.针对该题还有优化空间吗？
* 既然已经开辟了num1这个大数组的空间，其原意就是原地合并，所以可以考虑一下如何实现？
* 为了可以利用已经存在有效元素的数组1其余的空闲空间完成归并，可以考虑从数组末端完成归并。
* 时间复杂度：O（m + n）
* 空间复杂度：O（1）
* 如以下代码实现。
* @param num1
* @param num2
* @param m
* @param n
*/
public static void mergeTwoArrays(int[] num1, int[] num2, int m, int n) {
int p1 = m - 1, p2 = n - 1;
int i = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
num1[i --] = num1[p1] > num2[p2] ? num1[p1 --] : num2[p2 --];
}
while (p1 >= 0) {
num1[i --] = num1[p1 --];
}
while (p2 >= 0) {
num2[i --] = num2[p2 --];
}
}
private static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
ListNode node = this;
StringBuilder builder = new StringBuilder();
while (null != node) {
builder.append(node.val).append("->");
node = node.next;
}
builder.append(node);
return builder.toString();
}
}
/**
* 给出一个单链表，以O(n log n)的时间复杂度完成排序
* 显然，这题是往排序方面去考虑，因为题目没有表示结点值的数据特征，所以只能往经典排序方向去找一种时间复杂度为O(log n)的排序算法。
* 主流的无非两种：快速排序和归并排序。
* 快速排序为啥不采纳？它的时间复杂度与枢纽元素的位置相关，所以并非稳定的O(n log n)的时间复杂度去考虑，而且需要两个方向相反的指针，题目给出的是单链表，使用它实现排序无疑是额外增加不少消耗。
* 故只能在链表上完成归并排序.
* 时间复杂度：O（n log n）
* 空间复杂度：O（n）
* @param node
* @return
*/
public static ListNode mergeSortLinkedList(ListNode node) {
if (null == node) {
return null;
}
if (null == node.next) {
return node;
}
ListNode head = node, slow = node, fast = node;
//快慢指针法找到中位结点，注意只有两个结点的时候要可以收敛才能跳出递归。
while (null != fast.next) {
fast = fast.next;
if (null == fast.next) {
break;
}
slow = slow.next;
fast = fast.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode list1 = mergeSortLinkedList(head);
ListNode list2 = mergeSortLinkedList(mid);
return mergeSort(list1, list2);
}
private static ListNode mergeSort(ListNode head, ListNode mid) {
//虚拟结点
ListNode node = new ListNode(0);
ListNode ret = node;
while (null != head && null != mid) {
if (head.val < mid.val) {
node = node.next = head;
head = head.next;
}else {
node = node.next = mid;
mid = mid.next;
}
}
if (null != head) {
node.next = head;
}
if (null != mid) {
node.next = mid;
}
return ret.next;
}
/**
* 三面：多路归并排序
* 给K个长度为N的有序数组，合并成一个有序数组。
* 我：最初给出对应K个数组的K个指针，通过指针指向元素比较得出当前最小值，最小值指针前移，填入返回数组中，遍历(kn)就得到结果，时间复杂度：O（k^2n）但是面试时面试官直接指出给错了复杂度。。
* 面试官：还有优化空间吗？
* 我：（错了后当场脑塞了一会）还有利用数组头元素构造有序，后面维护有序再逐一取出即可。（思路是对的，但傻上心头的时候直接说给它排序，被面试官说这样明显还增加了时间复杂度的。。）
* 最后我还是太妄自菲薄了，当场否掉了自己的想法。这部分自主惨败收尾。
* 面试官：应该用某个数据结构处理，下去再想吧。
* 我：..应该用最小堆！！（下线过了一会后）
* 事实上这是一个方法。用最小堆维护K路数组，用对应的当前指针指向元素维护堆结构，取最小值后将其用对应的下一个元素代替并调整堆，如若没有下一元素就把堆的大小减一，再从剩余元素取下一最小值。如果纯粹在内存考虑时间复杂度，遍历（kn）次，每次有log k的调整堆消耗，时间复杂度为 O(kn log k)
* 事后查了一下，还有另一种数据结构可以达到几乎一样的优化程度取最小值的，就是胜者树和败者树，都是树形选择排序的变形。
* 我：还有没有其他更优的办法？
* 我：这就是命了，其实这方法并不陌生，也是以前跟同事讨论过处理归并的一种方法，所以发挥这么差的一次经历后，我真的经历一次挺痛苦的复盘：不要错过以前经历过的任何细节。
* 当时讨论的背景其实是一个二维表，每行每列都有序，按顺序输出所有元素。这二维数组的每一行不就是相当于一个一维有序数组嘛，不就是等价K路归并...吗..。
* 当时我提出的思路就是在一维实施归并，把一维数组当成一个元素，降维处理成每两个数组实施二路归并。元素总遍历次数为
* k / 2 * n + k / 4 * 2n + k / 8 * 4n + ... + k / k * kn / 2 = kn/2 log k 次，相对最小堆和胜败树可以减半。但有利也有弊端：纯粹在内存排序才有优势; 如果应用于外部排序，会额外增加磁盘IO次数。
*
* @param arrs
* @param start
* @param end
* @return
*/
public static int[] mergeSort(int[][] arrs, int start, int end) {
if (start >= end) {
return arrs[end];
}
int mid = start + ((end - start) >>> 1);
int[] arr1 = mergeSort(arrs, start, mid);
int[] arr2 = mergeSort(arrs, mid + 1, end);
return mergeTwoArrays(arr1, arr2);
}
private static int[] mergeTwoArrays(int[] arr1, int[] arr2) {
int p1 = 0;
int p2 = 0;
int length1 = arr1.length;
int length2 = arr2.length;
int[] rs = new int[length1 + length2];
int r = 0;
while (p1 < length1 && p2 < length2) {
rs[r ++] = arr1[p1] <= arr2[p2] ? arr1[p1 ++] : arr2[p2 ++];
}
while (p1 < length1) {
rs[r ++] = arr1[p1 ++];
}
while (p2 < length2) {
rs[r ++] = arr2[p2 ++];
}
return rs;
}
/**
* 败者树示例
* @param arrs
* @return
*/
public static int[] mergeSortByLoseTree(int[][] arrs) {
int k = arrs.length;
if (k == 0) {
return new int[0];
}
int n = arrs[0].length;
int c = k * n;
int[] rs = new int[c];
//败者树，完全二叉树，可以用数组存储，存储败者元素下标
int[] loseTrees = new int[k];
int[] prs = new int[k];
int[] externals = new int[k + 1];
for (int i = 0; i < k; i++) {
externals[i] = arrs[i][prs[i]];
}
externals[k] = Integer.MIN_VALUE;
//建立败者树
for (int i = 0; i < k; i++) {
loseTrees[i] = k;
}
for (int i = (k - 1); i >= 0; i--) {
adjustLoseTrees(loseTrees, externals, i, k);
}
int i = 0;
int p;
//循环(kn)次填充当前最小值
while (i < c) {
p = loseTrees[0];
rs[i ++] = arrs[p][prs[p] ++];
externals[p] = prs[p] >= arrs[p].length ? Integer.MAX_VALUE : arrs[p][prs[p]];
adjustLoseTrees(loseTrees, externals, p, k);
}
return rs;
}
/**
* 维护败者树的调整操作
* @param loseTrees
* @param externals
* @param s
*/
private static void adjustLoseTrees(int[] loseTrees, int[] externals, int s, int k) {
int tmp;
//t是结点（s + k）（映射externals[s]）的父结点
int t = s + ((k - s) >> 1);
while (t > 0) {
if (externals[s] > externals[loseTrees[t]]) {
tmp = s;
s = loseTrees[t];
loseTrees[t] = tmp;
}
t >>>= 1;
}
loseTrees[0] = s;
}
/**
* 一面：两个有序数组，求合并后的第K大元素。
* 面试官：有什么思路？
* 我：合并两个数组后取第K个元素。
* 面试官：复杂度怎么样？
* 我：设数组1长度为m,数组2长度为n，时间复杂度为O(m + n)，空间复杂度为O(m + n);
* 面试官：还有优化空间吗？
* 我：纯粹需要找到第K大元素，可以用二路指针比较遍历找到第K大直接返回即可，时间复杂度为O(K)，空间复杂度为O(1).（实际上当时差点懵了，因为觉得O(m + n)已经是线性复杂度，应该是最优了，差点不再尝试深层考虑）
* 面试官：实现一下。
* @param arr1
* @param arr2
* @param k
* @return
*/
public static int kthMergeArrays(int[] arr1, int[] arr2, int k) {
assert arr1 != null && arr2 != null && k >= 0;
int m = arr1.length;
int n = arr2.length;
//参数合法性校验
if (k > m + n) {
//不存在第K大
return -1;
}
int p1 = 0;
int p2 = 0;
int p = 0;
int t;
while (p1 < m && p2 < n) {
t = arr1[p1] < arr2[p2] ? arr1[p1 ++] : arr2[p2 ++];
if (++p == k) {
return t;
}
}
while (p1 < m) {
t = arr1[p1 ++];
if (++p == k) {
return t;
}
}
while (p2 < n) {
t = arr1[p2 ++];
if (++p == k) {
return t;
}
}
return -1;
}
/**
* 三面：两个正序数组，求两数组归并后的中位数元素。
* 面试官：说一下思路？
* 我：（想了一下。）可以用数组二路归并，归并到两数组总长度的一半时返回对应当前指针指向元素，即中位数。
* 面试官：空间上用了数组存储，还有优化空间吗？
* 我：（提示到我但当时还没接收到）我想想。
* 面试官：先给你20分钟实现一下。
* 我：（啪啪啪打起代码）...（写完了再检查）
* 面试官：中间这里的变量t1,t2什么意思？
* 我：刚刚您提示了我其实只需要返回中位数，就用了哨兵变量监视当前指针元素即可，到了中间长度返回即可。
* 面试官：面试完了。
* @param arr1
* @param arr2
* @return
*/
public static double middleVals(int[] arr1, int[] arr2) {
assert null != arr1 && null != arr2;
int m = arr1.length;
int n = arr2.length;
int total = m + n;
int limit = total >>> 1;
double rs = 0D;
int p1 = 0;
int p2 = 0;
//事实上可以省略，直接p1 + p2，但还要还原当时面试写法
int p = 0;
int t1 = -1, t2 = -1;
while (p1 < m && p2 < n) {
if (arr1[p1] < arr2[p2]) {
t1 = arr1[p1 ++];
}else {
t2 = arr2[p2 ++];
}
if (limit == ++ p) {
return (total & 1) == 0 ? (double)(t1 + t2) / 2 : Math.max(t1, t2);
}
}
while (p1 < m) {
t1 = arr1[p1 ++];
if (limit == ++ p) {
return (total & 1) == 0 ? (double)(t1 + t2) / 2 : Math.max(t1, t2);
}
}
while (p2 < n) {
t2 = arr2[p2 ++];
if (limit == ++ p) {
return (total & 1) == 0 ? (double)(t1 + t2) / 2 : Math.max(t1, t2);
}
}
return -1;
}
//---------------quickSort---------------------------------------------------
/**
* 快速排序
* @param arr
* @param start
* @param end
*/
private static void quickSort(int[] arr, int start ,int end) {
if (start >= end) {
return;
}
int partition = partition(arr, start, end);
quickSort(arr, start, partition - 1);
quickSort(arr, partition + 1, end);
}
private static int partition(int[] arr, int start, int end) {
int sp = start;
int ep = end;
int target = arr[sp];
while (sp < ep) {
while (sp < ep && arr[ep] >= target) {
ep --;
}
arr[sp] = arr[ep];
while (sp < ep && arr[sp] <= target) {
sp ++;
}
arr[ep] = arr[sp];
}
arr[sp] = target;
return sp;
}
}
2.
就一句提炼：归并排序的思想需要重点理清一下，抽象层面说它就是分而治之的一个入门典例。
现实情况：分治法，几乎是实际应用中多数非线性问题的重要解决思路。如上文，笔者四、五月时面试头部，前三轮都是归并。允许笔者大胆猜测一下，题库这类分治法的题目最近也是高频，当然大家可以一起集思广益，一起求证。希望大家可以收获自己满意的offer！