leetcode 算法 4. 寻找两个正序数组的中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int size1 = nums1.length;
int size2 = nums2.length;
int size = size1 + size2;
int target = size / 2;
if((size & 1) == 1){
// 奇数
return get(target+1,nums1,nums2);
}else {
// 偶数求均值
return (get(target,nums1,nums2) + get(target+1,nums1,nums2)) / 2.0;
}
}
public int get(int target,int[] nums1,int[] nums2){
int size1 = nums1.length;
int size2 = nums2.length;
//特殊条件
if(size1 == 0){
return nums2[target - 1];
}else if(size2 == 0){
return nums1[target - 1];
}
int index1 = -1;
int index2 = -1;
//退出循环的条件 1、目标只剩1个 2、任一数组已全部排除
while (target != 1 && index1 < size1 - 1 && index2 < size2 -1){
int num = target / 2;
int indexAdd1 = num;
int indexAdd2 = target - num;
if(index1 + indexAdd1 >= size1){
indexAdd1 = size1 - 1 - index1;
indexAdd2 = target - indexAdd1;
}else if(index2 + indexAdd2 >= size2){
indexAdd2 = size2 - 1 - index2;
indexAdd1 = target - indexAdd2;
}
if(nums1[index1 + indexAdd1] >= nums2[index2 + indexAdd2]){
target -= indexAdd2;
index2 = index2 + indexAdd2;
}else {
target -= indexAdd1;
index1 = index1 + indexAdd1;
}
}
if(index1 + 1 >= size1){
return nums2[index2 + target];
}else if(index2 + 1 >= size2){
return nums1[index1+target];
}else {
//两数组都未全部排除，取小
return Math.min(nums1[index1+1],nums2[index2+1]);
}
}
}
思路：
1、两个数组有序（认为是升序），求中位数变成合并数组的 第K小问题
总数奇数求一次；偶数求两次，取均值
2、求第K小，数组升序排列 比较 arr1 第k/2小 与 arr2 第k/2小数，根据结果可排除掉 k/2个数 类似于二分法
如 求 第 7 小，7/3 = 2 , arr1[2] >= arr2[2] ,变成 arr1[0..m] 与 arr2[3...n] 中 第 （7-3）小的问题，arr2中[0..2] 被排除。
需要考虑边界问题
其中一个数组长度过短，不足 再增长 target/2 （数组越界）其中一个数组已全部排除，则可以直接计算在另一个数组的下标 index + target
