题目
给定两个有序数组arr1和arr2，再给定一个整数k，返回所有的数中第k小的数。
题解
- 利用题目"在两个长度相等的排序数组中找到第上中位数"的函数
- 分类讨论
- k < 1 || k > lenShort + lenLong，无。
- k <= lenShort，在两个数组前k个做二分。
- k > lenLong，判断两个特例位置（特例部分是因为好计算可直接返回结果，并且抛去特例可满足两数组剩余待二分部份长度相等的条件），否则二分。
- lenShort<k<lenLong，判断一个特例位置，否则二分。
-
一些自己的理解
- 为什么一定要找中位数？因为抛掉(小、大)两边不可能的，求剩下的中位数仍旧是原来的中位数，可以不断进行压缩(O(logn)完成。)
- 为什么一定要两个数组长度相等？这样才能利用对称的性质不断取mid比不断删两端不可能的部分？(todo进一步思考)
- 时间复杂度O(log(min(M,N))),额外空间复杂度O(1)?可以做到，代码中是O(N)?
代码
public class Main {
public static void main(String args[]) {
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] arr2 = { 3, 4, 5 };
int k = 8;
int kthNum = getKthNum(arr1, arr2, k);
System.out.println(kthNum);
}
public static int getKthNum(int arr1[], int arr2[], int k) {
int lenShort = Math.min(arr1.length, arr2.length);
int lenLong = Math.max(arr1.length, arr2.length);
if (arr1 == null || arr2 == null) {
throw new RuntimeException("Array is invaild!");
}
if (k < 1 || k > lenShort + lenLong) {
throw new RuntimeException("K is invaild!");
}
if (k <= lenShort) {
return getUpMidian(arr1, arr2, 0, k - 1, 0, k - 1);//
}
if (k > lenLong) {
int pos1 = k - arr2.length - 1;// arr1需要特判的位置
if (arr1[pos1] >= arr2[arr2.length - 1]) {//
return arr1[pos1];
}
int pos2 = k - arr1.length - 1;// arr2需要特判的位置
if (arr2[pos2] >= arr1[arr1.length - 1]) {//
return arr2[pos2];
}
return getUpMidian(arr1, arr2, pos1 + 1, arr1.length - 1, pos2 + 1, arr2.length - 1);
} else {
int[] arrLonger = arr1.length == lenLong ? arr1 : arr2;
int[] arrShorter = arr1.length == lenShort ? arr1 : arr2;
int pos = k - lenShort - 1;
if (arrLonger[pos] >= arrShorter[lenShort - 1]) {// 较长数组需要特判的位置 //
return arrLonger[pos];
}
return getUpMidian(arrLonger, arrShorter, pos + 1, k - 1, 0, lenShort - 1);
}
}
// 获得两个排序数组上中位数
public static int getUpMidian(int arr1[], int arr2[], int l1, int r1, int l2, int r2) {
if (arr1.length == 1) {
return arr1[0] < arr2[0] ? arr1[0] : arr2[0];
}
while (l1 != r1) {
boolean oddFlag = (r1 - l1 + 1) % 2 == 1 ? true : false;
int mid1 = (l1 + r1) / 2;
int mid2 = (l2 + r2) / 2;
if (arr1[mid1] == arr2[mid2]) {
return arr1[mid1];
} else if (arr1[mid1] > arr2[mid2]) {
r1 = mid1;
l2 = oddFlag ? mid2 : mid2 + 1;
} else {
r2 = mid2;
l1 = oddFlag ? mid1 : mid1 + 1;
}
}
return arr1[l1];
}
}