力扣题4寻找两个正序数组的中位数

71 阅读 0 评论 47 点赞

我是靠谱客的博主平淡诺言，最近开发中收集的这篇文章主要介绍力扣题4寻找两个正序数组的中位数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

1.自己的解法：令middle=(length1+length2)/2。寻找中位数，需要分成两个数组元素总数为奇数和偶数两种情况。如果为奇数，中位数就是第middle大的数字；如果为偶数，中位数就是第middle大的数字和第middle+1大的数字之和的平均值。即题目最后就变成了寻找两个数组中第middle大和第middle+1大的数字，因此写一个函数来寻找第K大的数字。

在两个数组A、B内分别寻找第K/2个数字，即A[K/2-1]和B[K/2-1]，此时比较这两个数字的大小，有三种情况：

①A[K/2-1] < B[K/2-1]，那么说明在A中的前K/2个元素都不可能是第K个数，排除这几个数，

在剩余元素中继续寻找。

②A[K/2-1] > B[K/2-1]，那么说明在B中的前K/2个元素都不可能是第K个数，排除这几个数，

在剩余元素中继续寻找。

③A[K/2-1] = B[K/2-1]，可以归类到第一种情况。

利用递归即可，注意对每一次排除元素后对K的更新，对两个数组的新的起始下标的更新，要十分细致。还要注意第K大的下标为K-1。递归也可以改为循环进行。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLength = length1 + length2;
        int middleIndex = (length1 + length2)/2;

        if(totalLength % 2 == 1){//总数为奇数的情况
            return getKthNumber(nums1,nums2,middleIndex + 1,0,0);
        }else{//总数为偶数的情况
            return (double)(getKthNumber(nums1,nums2,middleIndex,0,0) + getKthNumber(nums1,nums2,middleIndex + 1,0,0)) / 2;
        }
    }
    //在两个数组中寻找第k大的数字
    public int getKthNumber(int[] nums1,int[] nums2,int k,int index1,int index2){
        int length1 = nums1.length;
        int length2 = nums2.length;

        //边界情况
        if(index1 == length1){//第一个数组无剩余元素时
            return nums2[index2 + k - 1];
        }
        if(index2 == length2){//第二个数组无剩余元素时
            return nums1[index1 + k - 1];
        }
        if(k == 1){//当k等于1时，直接比较两个数组剩余元素中的第一个元素即可
            return Math.min(nums1[index1],nums2[index2]);
        }

        //其余正常情况
        int half = k/2;
        int newIndex1 = Math.min(length1,half + index1) - 1;//判断数组下标是否会越界
        int newIndex2 = Math.min(length2,half + index2) - 1;
        if(nums1[newIndex1] <= nums2[newIndex2]){
            return getKthNumber(nums1,nums2,k - (newIndex1 - index1 + 1),newIndex1 + 1,index2);//更新剩余的k，以及新的数组起始下标
        }else{
            return getKthNumber(nums1,nums2,k - (newIndex2 - index2 + 1),index1,newIndex2 + 1);
        }

    }
}

2.其他解法。看到一个人使用了一个小技巧，这里也贴过来(来自评论@Wait想念)。我们分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。加入 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。

他的代码及其简练：

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        if(k == 1){
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
    }
}

主要是学习不区分奇偶情况的技巧。

题源：力扣