[程序员代码面试指南]第9章-在两个长度相等的排序数组中找到第k小的数(二分)

题目

给定两个有序数组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];
}
}
上一篇:剑指offer 27二叉搜索树与双向链表


下一篇:Android(java)学习笔记108:通过反射获取私有构造方法并且使用