[leetcode]4. Median of Two Sorted Arrays

本是古典何须时尚 2022-06-17 20:41 143阅读 0赞

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

这个题是要求两个已排好序的数组合并之后的中位数，时间复杂度要为O（log(m+n)）。

考虑到时间复杂度的要求，用两个游标从前往后找第k（假设第k个数刚好是中间那个数）个数的方法显然是不行的，于是只能另想办法。我们可以这样：把找第k个数分解成在nums1中找第k/2个数（设为mid1），在nums2中找第k/2个数（设为mid2）。倘若mid1大于mid2，则将nums2的前k/2个数去掉，问题转化为从nums1和新的nums2两个数组中找合并后第k-k/2个数；反之亦然。

边界条件是k=1时，直接返回两个数组的首位中较小的那个数。当某一数组元素全被删除后，直接返回另一数组的第k个元素即可。

接下来就是注意代码编写时谨防数组越界。

public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if((nums1.length + nums2.length) % 2 == 1){
                return findKthElement((nums1.length + nums2.length) / 2 + 1, nums1, 0, nums2, 0);
            }else{
                return (findKthElement((nums1.length + nums2.length) / 2, nums1, 0, nums2, 0) + findKthElement((nums1.length + nums2.length) / 2 + 1, nums1, 0, nums2, 0))/2;
            }
        }
        
        public double findKthElement(int k, int[] nums1, int start1, int[] nums2, int start2){
            if(start1 >= nums1.length){
                return (double)nums2[start2 + k - 1];
            }
            if(start2 >= nums2.length){
                return (double)nums1[start1 + k - 1];
            }
            if(k == 1){
                return (double)Math.min(nums1[start1], nums2[start2]);
            }
            int mid1 = Integer.MAX_VALUE, mid2 = Integer.MAX_VALUE;
            if(start1 + k/2 -1 < nums1.length){
                mid1 = nums1[start1 + k/2 -1];
            }
            if(start2 + k/2 -1 < nums2.length){
                mid2 = nums2[start2 + k/2 -1];
            }
            if(mid1 > mid2){
                return findKthElement(k - k/2, nums1, start1, nums2, start2 + k/2);
            }else{
                return findKthElement(k - k/2, nums1, start1 + k/2, nums2, start2);
            }
        }
    }