2つのソートされた配列からk番目に小さい要素を見つける

Question

サイズMとNのソートされた2つの配列が与えられた。私は時間の複雑さO（logM + logN）を持つアルゴリズムを実装しようとしていた。戦略は基本的に、長さ条件に基づいて2つのサブアレイからの中間インデックス要素を比較しています。

// Test case 1 
    // Works for all position except when kth is 6 
    int[] num1 = {6,7,8,9,10,11,12}; 
    int[] num2 = {1,2,3,4,5}; 

    // Test case 2 
    // Always print the next smallest element 
    int[] num3 = {1,3,5,7,9}; 
    int[] num4 = {2,4,6,8,10,12,14,16,18,20,22,24,30,40,50,56,77,35}; 


public static int findKth(int[] A, int p1, int r1, int[] B, int p2, int r2, int k){ 


    if (p1 > r1) { 
     return B[p2+k-1]; 
    } else if (p2 > r2) { 
     return A[p1+k-1]; 
    } 


    int midA = p1 + (int)Math.floor((r1-p1)/2);// Middle element from subarray A 
    int midB = p2 + (int)Math.floor((r2-p2)/2);// Middle element from subarray B 

    /** 
    * Compare the sum of number of elements from left-subarray up to middle element. 
    */ 
    if ((midA-p1+midB-p2+2) < k) { 
     // We don't need to the left-subarray based on the comparisons between middle element 
     if (A[midA] > B[midB]) { 
      return findKth(A, p1, r1, B, midB+1, r2, k-(midB-p2+1)); // 
     } else { 
      return findKth(A, midA+1, r1, B, p2, r2, k-(midA-p1+1)); // 
     } 
    } else { 
     // We don't need to the right-subarray based on the comparisons between middle element. 
     if (A[midA] > B[midB]) { 
      return findKth(A, p1, midA-1, B, p2, r2, k); 
     } else { 
      return findKth(A, p1, r1, B, p2, midB-1, k); 
     } 
    } 
} 

私が使用した戦略は正しいと感じました。しかし、上に示した2つのテストケースでは、間違った出力がある特定のk番目の値で出力されます。だから私は自分の戦略に何か間違っていると思った。誰がこの実装のどの部分が正しくないか簡単に説明できますか？ありがとう！

Answer 1

はすでにインスタンスhereとhereためStackOverflowの上でこの問題に良い解決策ありますので、私は唯一のバグを特定することに焦点を当てる：

この行は：

if ((midA-p1+midB-p2+2) < k) { 

使用するように変更する必要があります<=：

if ((midA-p1+midB-p2+2) <= k) { 

これは、この小さな例で必要な理由あなたが見ることができます：

A = {1,3} 
B = {2} 

他の変数は次のようになります。

p1 = p2 = r2 = midA = midB = 0 
r1 = 1 

そしてそう表現midA-p1+midB-p2+2は2になります。この場合、あなたは明らかにAの要素ではなく、一般的に、あなたのように、ifブロックの実行のためのKケースを含めてOKであることをBの要素のみ

注意を捨てたいですk（つまりあまりにも多くの）要素をそこに捨てることはありません。再帰呼び出しの最後の引数として渡される式は、常に最大でk-1です。MIDAまたはMIDBがうまく番目の要素というのk ^{の指標であるかもしれないとして、一方}

は、if式はKときelse部分に行く、間違っている、とそれはに投げられるでしょう。

Answer 2

スニペットにバグが見つかった場合は、私の回答が更新されます。

戦略は、基本的にその長さを条件に基づいて2つの 部分配列から中間のインデックス要素を比較している。今、あなたは、ロジックは除くあなたと全く同じである私のコードの外観を取ることができます。

私のコードの簡潔さと小さなサイズの主な違いは、最初の配列/インデックスの組の場合のパラメータを交換して関数を呼び出すことによってif-else条件（長さ条件）を避けることです。

public static int findKth(int[] A, int i, int[] B, int j, int k) { 

    // Here is the simple trick. We've just changed the parameter order if first array is not smaller. 
    // so that later we won't need to write if-else conditions to check smaller/greater stuff 
    if((A.length - i) > (B.length - j)) 
    { 
     return findKth(B, j, A, i, k); 
    } 

    if(i >= A.length) 
    { 
     return B[j + k - 1]; 
    } 
    if(k == 1) 
    { 
     return Math.min(A[i], B[j]); 
    } 

    int aMid = Math.min(k/2, A.length - i); 
    int bMid = k - aMid; 

    if(A[i + aMid - 1] <= B[j + bMid - 1]) 
    { 
     return findKth(A, i + aMid, B, j, k - aMid); 
    } 

    return findKth(A, i, B, j + bMid, k - bMid); 
} 

public static int findKthSmallestElement(int[] A, int[] B, int k) 
{ 
    if(k > A.length + B.length) 
     return -1; 

    return findKth(A, 0, B, 0, k); 
} 

時間複雑度はO(log(m + n))です。

Answer 3

#include <bits/stdc++.h> 
using namespace std; 

int findKthElement(int a[],int start1,int end1,int b[],int start2,int end2,int k){ 
    if(start1 >= end1)return b[start2+k-1]; 
    if(start2 >= end2)return a[start1+k-1]; 
    if(k==1)return min(a[start1],b[start2]); 
    int aMax = INT_MAX; 
    int bMax = INT_MAX; 
    if(start1+k/2-1 < end1) aMax = a[start1 + k/2 - 1]; 
    if(start2+k/2-1 < end2) bMax = b[start2 + k/2 - 1]; 

    if(aMax > bMax){ 
     return findKthElement(a,start1,end1,b,start2+k/2,end2,k-k/2); 
    } 
    else{ 
     return findKthElement(a,start1 + k/2,end1,b,start2,end2,k-k/2); 
    } 
} 

int main(void){ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
     int n,m,k; 
     cout<<"Enter the size of 1st Array"<<endl; 
     cin>>n; 
     int arr[n]; 
     cout<<"Enter the Element of 1st Array"<<endl; 
     for(int i = 0;i<n;i++){ 
      cin>>arr[i]; 
     } 
     cout<<"Enter the size of 2nd Array"<<endl; 
     cin>>m; 
     int arr1[m]; 
     cout<<"Enter the Element of 2nd Array"<<endl; 
     for(int i = 0;i<m;i++){ 
      cin>>arr1[i]; 
     } 
     cout<<"Enter The Value of K"; 
     cin>>k; 
     sort(arr,arr+n); 
     sort(arr1,arr1+m); 
     cout<<findKthElement(arr,0,n,arr1,0,m,k)<<endl; 
    } 

    return 0; 
} 

時間ComplexcityはO（ログ（のmin（m、n））を）私はあなたがのminheap/maxheapを使用することで、この問題を解決することができますね