【LeetCode04寻找两个正序数组的中位数】

简介: 【LeetCode04寻找两个正序数组的中位数】

【LeetCode04寻找两个正序数组的中位数】

01.题目简介:

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

算法的时间复杂度应该为 O(log (m+n))

案例

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

02.思路解释:

我们可以看出题目会给我们两个有序数组 然后合成一个有序数组 并且要求我们需要时间复杂度达到O(log (m+n))的水平,所以我们应该关注的是如何合并,我的思路是归并排序 也是一个比较常规的想法 因为归并排序的时机复杂度是O($nlogn$)的水平 其中归并排序的每一次的时间复杂度是O(n) 层数是O($logn$),由于我们题目已经给了我们两个有序的数组,所以我们只需要一次归并排序 但这种方法时间复杂度是O(m+n) 不满足要求 不过我这样也过了,官方数据不强,如果满足O(log (m+n))应该是要要求二分优化的 等我回头再做的时候进行优化补充。

03.代码:

class Solution 
{
    public static int[] msort(int[] q,int l,int mid,int r){// 归并排序
        int i=l,j=mid+1;
        int k=0;
        int[] temp=new int[q.length];
        while(i<=mid&&j<=r){
            if(q[i]<q[j]){
                temp[k++]=q[i++];
            }
            else{
                temp[k++]=q[j++];
            }
        }
        while(i<=mid){
            temp[k++]=q[i++];
        }
        while(j<=r){
            temp[k++]=q[j++];
        }
        return temp;
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int mid=nums1.length;
        int r=nums2.length;
        int[] temp=new int[mid+r];
        int k=0;
        for(int i=0;i<mid;i++)
            temp[k++]=nums1[i];
        for(int i=0;i<r;i++)
            temp[k++]=nums2[i];
        temp=msort(temp,0,mid-1,mid+r-1);
        if((mid+r)%2==0){
            double res=((double)temp[(mid+r-1)/2]+(double)temp[(mid+r-1)/2+1])/2;
            return res;
        }
        else {
            return temp[(mid+r-1)/2];
        }
    }
}
目录
相关文章
|
6月前
|
算法
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
63 0
|
5月前
|
SQL 算法 数据挖掘
LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】
LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】
|
6月前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
44 2
|
6月前
|
算法
【力扣】4. 寻找两个正序数组的中位数
【力扣】4. 寻找两个正序数组的中位数
|
6月前
|
存储 算法
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
|
6月前
|
存储 算法 Go
LeetCode第四题: 寻找两个正序数组的中位数
给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
|
6月前
|
算法 测试技术 C#
【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数
【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
107 2