LeetCode-4 2組の秩序配列は中位数を探す

トピックは、2つの正の配列の中位数を探すを参照してください.構想はLeetCodeの公式問題解から来ている.
2つのシーケンス配列の中位数を探して、mとnのサイズの2つのシーケンス(小さいから大きい)配列nums 1とnums 2を与えます.この2つのシーケンス配列の中位数を見つけて返してください.奇数であれば(m+n+1)/2番目の小さい数字を返し、偶数であれば(m+n)/2番目の小さい数と(m+n)/2+1番目の小さい数の2つの平均値を返します.
シナリオ1:集計.
シナリオ1.1真の統合
タイトルの2つの配列はすべて秩序配列であるため,集計後の新しい秩序配列を保存するために,空間サイズm+n m+n m+nの配列を開くことができる.2つの配列のうち1つの小さい数字を選択して集計後の新しい配列に配置するたびに、最後に新しい配列の中から問題の要求する中位数を選んで、返します.
シナリオ1.2擬似集計
実際、私たちは本当に空間の大きさがm+n m+n m+nのような大きな新しい配列を開く必要はありません.私たちは実は(m+n+1)/2番目の数字(偶数であれば2つ)の数字しか必要ありません.完全な配列を開いて保存する必要はありません.したがって、1つの数字を維持し、2つの配列間で2つの比較を行う場合、2つの配列間の最小の数字だけを残して、(m+n+1)/2番目の数字が見つかるまで下付きを増やします.このように空間複雑度はO(1)O(1)O(1)レベルに低下する.コードは次のとおりです.

class Solution {
     
public:
    double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
     
        int la = a.size();
        int lb = b.size();
        int i = 0, j = 0, id = 0, ans = 0, n = la + lb;
        if(n==1){
     
            for(auto t:a)return t;
            for(auto t:b)return t;
        }
        if(n%2){
     
            do{
     
                if(i<la&&j<lb){
     
                    if(a[i]<b[j]) ans = a[i++];
                    else ans = b[j++];
                }
                else if(i < la) ans = a[i++];
                else if(j < lb) ans = b[j++];
                id++;
            }while(id!=(n+1)/2);
            return ans;
        }
        else{
     
            double sum = 0;
            do{
     
                if(i<la&&j<lb){
     
                    if(a[i]<b[j]) ans = a[i++];
                    else ans = b[j++];
                }
                else if(i < la) ans = a[i++];
                else if(j < lb) ans = b[j++];
                id++;
                if(id==n/2||id==n/2+1){
     
                    sum += ans;
                }
            }while(id!=n/2+1);
            return sum / 2;
        }
    }
};

シナリオ2:二分検索
より一般的には,2つの秩序配列におけるK番目の小さい数を探すことを考慮した.2つの配列である以上、1番目の配列のK 2frac{K}{2}の2 K番目の数字は必ず1番目の配列の前のK 2−1frac{K}{2}−1 2 K−1番目の数字より大きく、2番目の配列のK 2frac{K}{2}の2 K番目の数字は必ず2番目の配列の前のK 2−1frac{K}{2}−1 2 K−1番目の数字より大きい.この2つの中で最も小さい数字は、せいぜい前のK 2−1+K 2−1=K−2frac{K}{2}−1+frac{K}{2}−1=K−2 K−1+2 K−1=K−2の2つの数字(なぜ「最も多い」のか、この数字が他の数字の前のK 2−1frac{K}{2}−1 2 K−1の数字よりも小さい可能性が高い)であり、K番目の小さい数字ではないので、この数字の後ろから次の二分検索を行う必要があり、同時にK 2frac{K}{2}2 K個の数字も排除され(この配列の中で容量がK 2frac{K}{2}2 K個未満であれば、その配列の総容量が減少し、排除された数字はt t t個と記す)、次回探すのはK−t−K−t−tの小さい数字であるべきである.考えがはっきりしたら、コードを書けばいいです.

class Solution {
     
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
     
        int m = nums1.size();
        int n = nums2.size();
        if ((m + n) %2 == 1){
     
            return getTopK((m+n)/2+1,m,n,nums1,nums2);
        }else{
     
            return (getTopK((m+n)/2,m,n,nums1,nums2)+getTopK((m+n)/2+1,m,n,nums1,nums2))/2.0;
        }
    }
    int getTopK(int k, int m, int n, vector<int>& nums1, vector<int>& nums2){
     
        int index1 = 0, index2 = 0;
        int mid_index1,nums_index1;
        int mid_index2,nums_index2;
        while(true){
     
            if(index1 == m){
     
                return nums2[index2 + k - 1];
            }
            if(index2 == n){
     
                return nums1[index1 + k -1];
            }
            if(k == 1){
     
                return min(nums1[index1],nums2[index2]);
            }
            mid_index1 = min(index1 + k / 2 - 1 , m-1);
            mid_index2 = min(index2 + k / 2 -1 ,n-1);
            nums_index1 = nums1[mid_index1];
            nums_index2 = nums2[mid_index2];
            if (nums_index1 < nums_index2){
     
                k -= mid_index1 - index1 + 1;
                index1 = mid_index1  +1;
            }else{
     
                k -= mid_index2 - index2 + 1;
                index2 = mid_index2  + 1;
            }
        }
    }
};