【算法】【算法杂谈】两个排序数组中找第k小的数

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定两个数组arr1，arr2，求arr1和arr2合并到一起后，第k小的数是什么
如：
arr1 = [1,2,3]
arr2 = [3,4,5,6]
求第3小的数
结果为3

解决方案

原问题：
参考相同长度的排序数组求上中位数的解法：

https://editor.csdn.net/md?not_checkout=1&articleId=131177400

接下来介绍如何将两个长度不相同的排序数组能够套用上面的办法
首先假设短数组长度10 [0…9]
长数组长度27 [0…26]
总长度为37

• 如果第k小的数中k<shor.len ,也就是k <=10,那么长数组中角标大于k的部分是不会存在第k小的数的，因为后面的数至少都大于k个数，所以问题就变成了 arr1[0…k-1] 和arr2[0…k-1]之间求第k小的数问题了,套用参考即可
• 如果第k小的数范围在 37 - 10 <= k < 37 之间时， 我们知道k后面最多只能有9个数，所以短数组都能选择，长数组可以选的范围只能是27-10到27的范围之间，问题又变成了相同长度数组求上中位数的问题，套用参考即可
• 最后k如果都不满足上面的条件，也就是 10<k<37-10，该怎么办呢？我们假设k = 16，16前面必须有15个数，后面必须有20个数，那么现在我们看下如何补齐。前面15个数，短数组如果全补上去，还剩5个数需要长数组填，那么长数组从第5个位置开始比较，查看是否真的短数组需要补上去(短数组的最大值 < 长数组的第5个位置)，如果不小于则从第6个位置开始计算
  后面20个如果将短数组全补上去还剩10个需要补，所以长数组中最多能到低16个开始往回走，我们发现长度刚好是10！直接套用公式即可。

代码编写

java语言版本

原问题：
原问题：

   /*** 二轮测试：两个排序数组中找到第k小的数* @return*/public static int findKMinFromSortArrCp1(int[] arr1, int[] arr2, int k) {if (k < 1|| arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0|| (arr1.length + arr2.length < k)) {throw new RuntimeException("非法入参");}int[][] compareRes = compareArr(arr1, arr2);int[] shortArr = compareRes[0];int[] longArr = compareRes[1];if (k < shortArr.length) {return getUpMidFromSameLenArr(shortArr, 0, k-1, longArr, 0, k-1);}else if (k > longArr.length) {// 后面需要有几个元素int sub = (shortArr.length + longArr.length) - k;int start1 = shortArr.length - 1 - sub;int start2 = longArr.length - 1 - sub;if (longArr[start2] >= shortArr[shortArr.length - 1]) {return longArr[start2];}if (longArr[shortArr.length - 1] <= shortArr[start1]) {return longArr[shortArr.length-1];}return getUpMidFromSameLenArr(shortArr, start1+1, shortArr.length-1, longArr, start2+1, longArr.length-1);}else {int sub = (shortArr.length + longArr.length) - k;// 后面必须凑够20个int start2 = k - shortArr.length - 1;// 排除一个值否则长度不相等if (shortArr[shortArr.length - 1] <= longArr[start2]) {return longArr[start2];}else {start2++;}int end2 = longArr.length - (sub - shortArr.length) - 1;return getUpMidFromSameLenArr(shortArr, 0, shortArr.length-1, longArr, start2, end2);}}/*** 从两个数组中相同长度的子数组部分中求上中位数* @param arr1* @param start1* @param end1* @param arr2* @param start2* @param end2* @return*/private static int getUpMidFromSameLenArr(int[] arr1, int start1, int end1, int[] arr2, int start2, int end2) {int mid1 = 0;int mid2 = 0;while (start1 < end1) {// 获取中间值mid1 = (start1 + end1)/2;mid2 = (start2 + end2)/2;if (arr1[mid1] == arr1[mid2]) {return arr1[mid1];}else {// 计算长度偶数或者奇数，偶数0，奇数1int offset = ((end1 - start1 + 1) & 1) ^ 1;if (arr1[mid1] > arr2[mid2]) {// 奇数的话不需要调整数组大小直接割end1 = mid1;start2 = mid2 + offset;}else {start1 = mid1 + offset;end2 = mid2;}}}return Math.min(arr1[start1], arr2[start2]);}/*** 比较出来两个数组的长短* @param arr1* @param arr2* @return compareRes[0] 为短数组*/private static int[][] compareArr(int[] arr1, int[] arr2) {return arr1.length > arr2.length ? new int[][]{arr2, arr1} : new int[][]{arr1, arr2};}public static void main(String[] args) {System.out.println(findKMinFromSortArrCp1(new int[]{1,2,3}, new int[]{3,4,5,6}, 6));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题最后分析的地方为什么能够恰好是10呢？这个我仔细想了一下
首先 长数组的起始位置 k-10
结束位置，27-((37-k)-10) = k
那么结束位置 - 起始位 = 10 = 短数组长度

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给[e-mail]
再次感谢左大神对我算法的指点迷津！