与えられた配列内の逆位数を数えよう

Question

私はこの問題をマージソートで解決しようとしましたが、私の解決策には何か問題があります。配列をマージする際に逆数を調べました。 誰かが問題を見つけるのを助けることができますか？

void merge(int arr[], int l, int m, int r) 
{ 
    int n1=m-l+1; 
    int n2=r-m; 
    int left[(n1+1)]; 
    int right[(n2+1)]; 
    for(int i=0;i<n1;i++){ 
     left[i]=arr[l+i]; 
    } 
    for(int j=0;j<n2;j++){ 
     right[j]=arr[m+j+1]; 
    } 
    left[n1]=INT_MAX; 
    right[n2]=INT_MAX; 
    int i=0, j=0; 
    //int inv=0; 
    for(int k=l;k<=r;k++){ 
     if(left[i]<=right[j]){ 
      arr[k]=left[i]; 
      i++; 
     } 
     else{ 
      arr[k]=right[j]; 
      j++; 
      inv+=(m-i); 
     } 
    } 
    //return inv; 
} 

void mergeSort(int arr[], int l, int r) { 
    int inv=0; 
    if (l < r) { 
     int m = l+(r-l)/2; 
     mergeSort(arr, l, m); 
     mergeSort(arr, m+1, r); 
     merge(arr, l, m, r); 
    } 
    // return inv; 
} 

Answer 1

あなたはm - iのinv instadにn1 - iを追加することが必要であることを除いて、すべてを正しく行っています。

その理由は次のとおりです。 「正しい」部分から数値を取るとき、それはまだ取られていない「左」部分の任意の数よりも低く、したがってそのような対は反転を形成する。 「左」部分の未処理項目の数はn1 - 1 [実際の配列の最後の数字です。 INT_MAXはインデックスn1] - i [現在の未処理アイテム] + 1 [インデックスが含まれているため]に格納され、簡略化するとn1 - iになります。

も反転数nは、配列のサイズであるO(n^2)、のように高くなることがありますのでご注意ください、あなたがlong long変数に反転回数を保存することがあります。

コードの最終バージョン：

int merge(int arr[], int l, int m, int r) 
{ 
    int n1=m-l+1; 
    int n2=r-m; 
    int left[(n1+1)]; 
    int right[(n2+1)]; 
    for(int i=0;i<n1;i++){ 
     left[i]=arr[l+i]; 
    } 
    for(int j=0;j<n2;j++){ 
     right[j]=arr[m+j+1]; 
    } 
    left[n1]=INT_MAX; 
    right[n2]=INT_MAX; 
    int i=0, j=0; 
    int inv=0; 
    for(int k=l;k<=r;k++){ 
     if(left[i]<=right[j]){ 
      arr[k]=left[i]; 
      i++; 
     } 
     else{ 
      arr[k]=right[j]; 
      j++; 
      inv += n1 - i; 
     } 
    } 
    return inv; 
} 

int mergeSort(int arr[], int l, int r) { 
    int inv=0; 
    if (l < r) { 
     int m = l+(r-l)/2; 
     inv += mergeSort(arr, l, m); 
     inv += mergeSort(arr, m+1, r); 
     inv += merge(arr, l, m, r); 
    } 
    return inv; 
}