栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

分享一道力扣困难题~寻找两个有序数组的中位数(Java)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

分享一道力扣困难题~寻找两个有序数组的中位数(Java)

目录

解题思路1

具体代码

解题思路2 

 具体代码


 

题目描述:给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

题目链接:寻找两个有序数组的中位数

解题思路1

在我一开始看到这个题目的时候,首先想到的方法就是合并两个数组,边合并边排序,之后取中间的数字即可,这种写法是简单,可是时间复杂度是O(m+n),而题目的要求是O(log (m+n)),显然这种方法是行不通的。

 从最大值开始依次比较插入新的数组,完成后取中间值即可.

具体代码
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLength = length1 + length2;
        int[] newNums = new int[totalLength];
        length1 -= 1;
        length2 -= 1;
        totalLength -= 1;
        while(length1 >= 0 && length2 >= 0) {
            if(nums1[length1] > nums2[length2]) {
                newNums[totalLength--] = nums1[length1--];
            }else {
                newNums[totalLength--] = nums2[length2--];
            }
        }
        while(length1 >= 0) {
            newNums[totalLength--] = nums1[length1--];
        }
        while(length2 >= 0) {
            newNums[totalLength--] = nums2[length2--];
        }
        totalLength = nums1.length + nums2.length;
        int mid = totalLength/2;
        if(totalLength % 2 == 1) {
            return (double)newNums[mid];
        }
        return (newNums[mid] + newNums[mid-1])/2.0;
    }
}

解题思路2 

这种解法的时间复杂度为题目要求的O(log (m+n)),且空间复杂度为O(1),显然优于第一种思路。

该种思路的主要思想为二分思想,每比较一次就缩小一次范围,具体思路如下所示:

首先,整体分为两种情况,一种是两个数组所有数字加起来为偶数,另一种是奇数

当为奇数时,直接寻找中间的即可

 

当为偶数时,需要找到中间的两个相加再除以二

经过上述分析,可以大致搭建出整个程序的框架,之后再去寻找指定下标的数字即可.

 以如下数组为例

 这两个数组元素个数和为奇数,因此只需找到中间那一个即可,首先根据数组长度可以得出要寻找的是下标为(nums1 + nums2) / 2,即下标为4的元素,即第五个元素。

定义一个函数来寻找两个数组中第k小的元素,传入两个数组和k.

 在该函数中,首先定义出index1和index2,初始化为0.

根据k,index1和index2确定出需要比较的下标,并进行比较.3<8,因此可以排除3左边的数字,此时再更新k的值,改变index1即可

则继续根据 来确定要比较的下标,比较过后继续更改index以及k的值,第二次比较过后,k == 2,index1等于3,index2等于0,此时index1等于length1,对其特殊判断即可得到第k小的数.

            if(index1 == length1) {
                return nums2[k+index2-1];
            }

 

 

同理,当index2等于length2时,也需要对其特殊处理

            if(index2 == length2) {
                return nums1[k+index1-1];
            }

如果k == 1时,未出现上述两个条件,例如一个数组是[1,2],另一个数组是[3]时,直接返回下标为index1和index2两个数较小的那一个即可 

            if(k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

 具体代码
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLength = length1 + length2;
        if(totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double ret = getKthNumber(nums1, nums2, midIndex+1);
            return ret;
        }else {
            int midIndex1 = totalLength / 2 - 1;
            int midIndex2 = totalLength / 2;
            double ret = (getKthNumber(nums1, nums2, midIndex1+1) + getKthNumber(nums1, nums2, midIndex2+1)) / 2.0;
            return ret;
        }
    }
    private double getKthNumber(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int index1 = 0;
        int index2 = 0;
        while(true) {
            if(index1 == length1) {
                return nums2[k+index2-1];
            }
            if(index2 == length2) {
                return nums1[k+index1-1];
            }
            if(k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            int half = k/2;
            int newIndex1 = Math.min(index1+half, length1)-1;
            int newIndex2 = Math.min(index2+half, length2)-1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if(pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/961444.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号