[力扣] 4. 寻找两个有序数组的中位数

链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays

题目

[困难] 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。

示例

示例 1:

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

题解

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //双指针遍历,保证有序遍历
        //遍历 (nums1.length+nums2.length)/2+1次,同时记录最大值和次大值,即指针最后一次和倒数第二次遍历的值
        //如果是奇数返回最大值,如果是偶数返回最大值和次大值的平均值
        int i1=0;
        int i2=0;
        int len = nums1.length+nums2.length;
        int mid = len/2;
        int ult=0;
        int penult=0;
        while(i1+i2<=mid){
            if(i1>=nums1.length) {penult = ult; ult=nums2[i2]; i2++; }
            else if(i2>=nums2.length)  {penult = ult; ult=nums1[i1]; i1++;}
            else if(nums1[i1]>nums2[i2])  {penult = ult; ult=nums2[i2]; i2++;}
            else  {penult = ult; ult=nums1[i1]; i1++;}
        }

        if(len%2==1) return ult;
        else return (ult+penult)/2.0;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容