思路分析
一想到就是二路归并,但是这个复杂度肯定不符合题目要求。哎,自己是想不到新思路了,还是看题解。
二分找第k小的数,每次对两个数组取前k/2个数,比较最后一个。较小的数组可以保证这前k/2个数肯定都比第k小的数更小,因此可以舍弃,对于新的两个数组,递归求解第k小的数这一问题。(实际代码中通过修改起始索引位置形成新数组)
非常巧妙的一个思路,看懂后恍然大悟,但是实际实现过程中要充分考虑各种边界情况,比如其中一个数组为空时,k=1时。
代码实现
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
// 统一奇偶数情况的表达形式
// 待求数据的索引顺序, 从小到大排列, 下标从1开始
int leftIndex = (len1 + len2 + 1) / 2;
int rightIndex = (len1 + len2 + 2) / 2;
int leftNum = getKthNum(leftIndex, nums1, nums2, 0, len1, 0, len2);
int rightNum = getKthNum(rightIndex, nums1, nums2, 0, len1, 0, len2);
return (leftNum + rightNum) / 2.0;
}
/**
* 求两个正序数组中第K小的数
*
* @param k 索引号
* @param nums1 数组1
* @param nums2 数组2
* @param head1 数组1头指针
* @param len1 数组1剩余长度
* @param head2 数组2头指针
* @param len2 数组2剩余长度
* @return 第K小的数
*/
private int getKthNum(int k, int[] nums1, int[] nums2, int head1, int len1, int head2, int len2) {
// 如果有一组序列已被全部舍弃, 直接在另一组序列上即可确定
if (len1 == 0) {
return nums2[head2 + k - 1];
}
if (len2 == 0) {
return nums1[head1 + k - 1];
}
// 求第1小的数直接比较即可
if (k == 1) {
return Math.min(nums1[head1], nums2[head2]);
}
// 确定要舍弃的项数
int drop = Math.min(k / 2, Math.min(len1, len2));
int index1 = head1 + drop - 1;
int index2 = head2 + drop - 1;
// 同一索引上数值较小的序列, 前面的数值将被舍弃
if (nums1[index1] <= nums2[index2]) {
return getKthNum(k - drop, nums1, nums2, index1 + 1, len1 - drop, head2, len2);
} else {
return getKthNum(k - drop, nums1, nums2, head1, len1, index2 + 1, len2 - drop);
}
}
}