【 LeetCode 热题 HOT 100】4. 寻找两个正序数组的中位数 (C++ 遍历 分类讨论)

简介: 【 LeetCode 热题 HOT 100】4. 寻找两个正序数组的中位数 (C++ 遍历 分类讨论)

题目链接

题意:

寻找两个已经从小到大排好序的数组的中位数。

思路:

大概是比较投机取巧的一种方法,时间复杂度为O ( n )的。

先计算两个数组的元素个数总和,分奇偶讨论。

如果是奇数的话,中位数是第(sum+1)/2个数;否则,是中间两个数的平均数。

分别设两个指针tx,ty,用来遍历两个数组。

每次都让当前数的指针前移。

最后维护下中位数就好了~

代码:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int x=nums1.size(),y=nums2.size();
        int sum=x+y;
        double ans;
        if(sum%2){
            int t=(sum+1)/2;
            //cout<<t<<endl;
            int tx=0,ty=0;
            while(t--){
                if(tx<x&&ty<y){
                    if(nums1[tx]<nums2[ty]) ans=nums1[tx],tx++;
                    else ans=nums2[ty],ty++;
                }
                else if(tx<x&&ty==y){
                    ans=nums1[tx],tx++;
                }
                else if(ty<y&&tx==x){
                    ans=nums2[ty],ty++;
                }
                //cout<<tx<<" "<<ty<<" "<<ans<<endl;
            }
        }
        else{
            double ans1,ans2;
            int t=sum/2+1;
            int tx=0,ty=0;
            while(t--){
                ans1=ans2;
                if(tx<x&&ty<y){
                    if(nums1[tx]<nums2[ty]) ans2=nums1[tx],tx++;
                    else ans2=nums2[ty],ty++;
                }
                else if(tx<x){
                    ans2=nums1[tx],tx++;
                }
                else if(ty<y){
                    ans2=nums2[ty],ty++;
                }
            }
            ans=(ans1+ans2)/2.0;
        }
        return ans;
    }
};
目录
相关文章
|
7天前
|
存储 C++
C++指针数组
C++指针数组
16 1
|
1天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
14 1
|
1天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
15 1
|
1天前
|
存储 自然语言处理 C语言
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(上)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
16 1
|
1天前
|
算法 C语言 容器
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
17 7
|
1天前
|
C语言
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
13 1
|
1天前
|
算法 C语言 C++
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
10 1
|
2天前
|
存储 前端开发 算法
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(下)
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣
5 0
|
2天前
|
存储 C语言
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(中)
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣
8 0
|
2天前
|
算法 C语言 容器
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(上)
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣
12 0