プログラミング面接の質問（配列反転）

Question

可能性の重複：
Counting inversions in an array

これは、私は数ヶ月前に開発者の仕事のために会社がインタビューされたときに私が持っていたプログラミングの質問です。 N個の整数の配列Aを考える

、反転アレイのは、インデックスの任意のペアとして定義されている（a、b）は、その結果< BおよびA [B] < A [A]。

関数を書く：

int inversion_count(int A[], int n); 

Aに反転数を計算し、または-1を返し、そのような数が10億を超える場合があります。たとえば、次の配列

A[0]=-1 A[1]=6 A[2]=3 A[3]=4 A[4]=7 A[5]=4 

で4つの反転あります

(1,2) (1,3) (1,5) (4,5) 

はとても機能は4

を返す必要があり、私は非常に一般的な方法でこの問題を解決：ダブルループを使用して。

int i, j; 
long count; 
for (i = 0; i < n; i++) { 
    for (j = i+1; j < n; j++) { 
     if (A[i] > A [j]) count++; 
     if (count > 1000000000) break; // exit loop 
    } 
    if (count > 1000000000) break; // exit loop 
} 
if (count > 1000000000) return -1; 
else return count; 

したがって、実行時間は：O（nsquare）であり、効率的ではないと言われました。私は今、この問題を解決する別の方法を考えています。おそらくn log nアルゴリズムを使用していますが、私はまだそれを理解していません。何か案は？

Answer 1

この回答はO（n log n）アルゴリズムについて説明しています：Counting inversions in an array。

まず、ソート（O（n log n））をソートし、バイナリ検索を使用してO（n log n）という要素を見つけ、O（n log n）を求めます。