前言

當前所有算法都使用測試用例運行過，但是不保證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個開始往回走，我們發(fā)現長度剛好是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源碼可郵件給2260755767@qq.com
再次感謝左大神對我算法的指點迷津！