algorithm - arr[i] < arr[j] および i < j となるように、配列内のインデックスのペアの総数をカウントします

Question

ここで質問するつもりだったのですが、インデックスの条件について言及するのを忘れていたので、新しい質問を作成しました。

質問にはソートされていない配列が与えられ、とのi, jようなインデックスのペアの総数を見つけます。複雑さは線形またはそれに近いものにする必要があります。i < jarr[i] < arr[j]

Answer 1

ターゲットが のi < jようなペアの数を見つけた場合arr[i] > arr[j]、それは反転カウントになります。これは、配列をマージソートし、各アイテムが移動した値の数をカウントすることによって決定できます。

ここで、降順で並べ替えると、同じことができます。

int pairs_count(int[] arr, int lo, int hi) {
    if (hi <= lo) return 0;
    int mid = (lo+hi)/2;
    int count = pairs_count(arr, lo, mid);
    count += pairs_count(arr, mid+1,hi);
    count += merge(arr, lo, mid, hi);
    return count;
}

int merge(int[] arr, int lo, int mid, int hi) {
    int[] scratch = new int[hi-lo+1];
    int l = lo, r = mid+1, k = 0, count = 0;
    while(l <= mid && r <= hi) {
        if (arr[r] > arr[l]) {
            scratch[k++] = arr[r++];
            count += mid-l+1;
        } else {
            scratch[k++] = arr[l++];
        }
    }
    while(l <= mid) {
        scratch[k++] = arr[l++];
    }
    while(r <= hi) {
        scratch[k++] = arr[r++];
    }
    for(k = 0; k < scratch.length; ++k) {
        arr[lo+k] = scratch[k];
    }
    retrun count;
}

で呼び出しますpairs_count(arr, 0, arr.length - 1);。