欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode第4题_寻找两个有序数组的中位数

程序员文章站 2024-03-15 22:34:30
...

LeetCode第4题_寻找两个有序数组的中位数

  • 题目:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
  • 个人解法:开始时想到将两个数组完全合并,再找中位数。这种做法过于暴力,其实不必完全合并,只需合并到中间那两个或一个就可以了。于是有了下面的做法。代码中有很多重复代码,希望可以优化一下。
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int a=nums1.length+nums2.length;
        int nums[]=new int[a];
        if(a%2==0){
            for(int i=0,j=0,k=0;k<a/2+1;k++){
                if(i>=nums1.length){
                    nums[k]=nums2[j++];
                }else if(j>=nums2.length){
                    nums[k]=nums1[i++];
                }else if(nums1[i]<=nums2[j]){
                    nums[k]=nums1[i++];
                }else{
                    nums[k]=nums2[j++];
                }
            }
            double ans=nums[a/2-1]+nums[a/2];
            return ans/2;
        }else{
           for(int i=0,j=0,k=0;k<=(a-1)/2;k++){
                if(i>=nums1.length){
                    nums[k]=nums2[j++];
                }else if(j>=nums2.length){
                    nums[k]=nums1[i++];
                }else if(nums1[i]<=nums2[j]){
                    nums[k]=nums1[i++];
                }else{
                    nums[k]=nums2[j++];
                }
            }
            return nums[(a-1)/2];
        }
              
    }
}
  • 解法二:另一种思路,不需要合并,只需要记录一下。
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int left = -1, right = -1;
        int aStart = 0, bStart = 0;//记录每个数组读取的个数
        for (int i = 0; i <= len / 2; i++) {
             left = right;
             //判断第一个数组未读完并且第二组数读完或第一组数比第二组数小
             if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
                    right = nums1[aStart++];
                    } else {
                         right = nums2[bStart++];
                    }
             }
        //通过按位与判断奇偶性     
        if ((len & 1) == 0)
             return (left + right) / 2.0;
        else
             return right;
    }
}
  • 解法三:二分法+递归。小菜鸟看了别人的算法,真真是惊为天人。将中位数转换为求第k个最小数。在两个数组中取第k/2个数比较大小,小数之前的所有数都不可能是第k个最小数,故去掉他们。第二次相当于求新的两个数组中第k-k/2个最小数,由此递归。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并,如果是奇数,会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

作者:windliang
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。