前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~
问题介绍
原问题
给定两个数组arr1，arr2，求arr1和arr2合并到一起后，第k小的数是什么
如：
arr1 = [1,2,3]
arr2 = [3,4,5,6]
求第3小的数
结果为3
解决方案
原问题：
参考相同长度的排序数组求上中位数的解法：
接下来介绍如何将两个长度不相同的排序数组能够套用上面的办法
首先假设短数组长度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，奇数1
int 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 = 短数组长度