leetcode 4の2つのソート配列の中位数C++

参考記事:1https://blog.csdn.net/yutianxin123/article/details/52189127?utm_source=blogxgwz6
                  2 https://blog.csdn.net/qq_32320399/article/details/81518476
                  3 https://blog.csdn.net/codekiller_/article/details/61419120
方法1:

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    
 double findK(vector&a, int lena, vector&b, int lenb, int k)
    {
        int i = 0, j = 0;

        for(; i < lena && j < lenb; )
        {
            k--;
            if (a[i]= lena) ? b[j+k-1] : a[i+k-1];
    }

    double findMedianSortedArrays(vector &nums1, vector &nums2) {

       int m = nums1.size(), n = nums2.size();
       int left = (m + n + 1 ) / 2, right = (m + n + 2) / 2;

        //        ，       
       return (findK(nums1, m, nums2, n, left) + findK(nums1, m, nums2, n, right)) / 2.0;
    }

};

コードの最初の関数はleetcodeの上位数のコードを表示する上で発見した共通性であり、コードの実行時間をある程度減らすことができ、具体的な詳細は文章の最初の接続を表示することができます.
方法1は主に1つの探索を利用して小さいから大きいまでK番目の数の関数findK()を並べ替えて操作して、最後に主な関数findMedianSortedArrays()はfindK()を呼び出して、中位数を求める小さい技巧を利用して、m+nが奇数である場合、2つの同じ中位数を返して更に2で割る.m+nが偶数である場合、中間(m+n)/2と(m+n)/2−1の位置の数の和を2で割って、結果に合致する.上のコードの時間的複雑度はO(m+n)であるが,問題はO(log(m+n))であり,結果は通過したが,明らかに分治アルゴリズムを用いて問題を解決することが要求される.
方法2:

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int findK(vector &s, int m, vector &l, int n, int k){
        //  m < n
        if (m > n)
            return findK(l, n, s, m, k);
        if (m == 0)
            return l[k - 1];
        if (k == 1)              
            return min(s[0], l[0]);
        //       
        int i = min(m, k / 2), j = min(n, k / 2);   
        if (s[i - 1] > l[j - 1])   
           return findK(s, m, l + j, n - j, k - j); 
        else   
           return findK(s + i, m - i, l, n, k - i);  
        return 0;      }  
    }

    double findMedianSortedArrays(vector &nums1, vector &nums2) {

       int m = nums1.size(), n = nums2.size();
       int left = (m + n + 1 ) / 2, right = (m + n + 2) / 2;

        //        ，       
       return (findK(nums1, m, nums2, n, left) + findK(nums1, m, nums2, n, right)) / 2.0;
    }

};

方法2は主に二分法を用い,探索範囲を絶えず縮小し,探索時間を短縮し,複雑度はO(log(m+n))である.