Count Inversions
整数のリスト nums が与えられたとき、転倒数を返してください。転倒とは、i < j かつ nums[i] > nums[j] を満たすインデックスの組、つまり大きい値が小さい値より前にある組のことです。値が等しい場合は転倒にならず、ソート済みのリストには転倒はありません。
関数
- numsinteger-array
- 整数のリスト
- 戻り値integer
- nums[i] > nums[j] である i < j の組の数
制約
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- 答えは最大でも
n(n-1)/2 < 2 × 108なので、符号付き32ビット整数に収まります。
例
- 入力
- nums = [5, 3, 8, 1, 4]
- 出力
- 6
- 説明
- 5は3、1、4より前にあります：3組です。3は1より前にあり、8は1と4より前にあります：さらに3組です。1と4は順番どおりなので、合計は6です。
- 入力
- nums = [2, 2, 2, 1]
- 出力
- 3
- 説明
- 3つの2はいずれも1より前にあるため、転倒数は3です。等しい2同士は決して数えません。転倒となるには、前にある値が厳密に大きい必要があるからです。
- 入力
- nums = [-1, 0, 7, 7]
- 出力
- 0
- 説明
- リストはソートされており、等しい2つの7はカウントされないため、答えは0です。
発展問題
nums[i] > 2 × nums[j]の場合にのみペアとして数えると、何が変わるでしょうか？マージソートで引き続きO(n log n)でこれらのペアを数えられるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リストを左半分と右半分に分けます。各転倒は、左半分の中、右半分の中、または左右それぞれに1つずつ値があるペアのいずれかです。3つのグループを別々に数えられますか？
それぞれの半分をソートしても、中央をまたぐペアの数は変わりません。左側の値はすべて右側の値より左にあるままだからです。また、両方の半分がソートされていれば、中央をまたぐペアは1つずつではなく、まとめて数えることができます。
マージソートを使います。ソート済みの2つの半分をマージするとき、右半分から値を取るたびに、その値は左半分に残っているすべての値より小さいため、左半分に残っている値の個数を加算します。同じ値の場合は左半分から取ることで、等しい値が数えられることはありません。
解説
すべてのペアを調べるには、約 n² / 2 回の比較が必要です。マージソートでは、ペアをまとめて数えます。マージ中に右半分の値を配置するとき、まだ待機している左側の値はすべてそれより大きく、かつ先に現れていました。引き算を1回するだけで、そのまとまり全体を数えられるため、カウントにかかるコストは O(n log n) のソートを超えません。
すべてのペアを確認する
正しいが、最大のテストでは終わらない
考え方
各インデックス i について、それより後のすべてのインデックス j を確認し、nums[i] > nums[j] の場合に 1 を加えます。これが定義であり、厳密な比較では等しい値は対象外になります。
比較回数は n(n-1)/2 です。2 × 10^4 個の値では約 2 × 10^8 回になり、n を 2 倍にすると 4 倍になります。
アルゴリズム
count = 0に設定します。- 0から
n-1までの各iについて、またi + 1からn-1までの各jについて、nums[i] > nums[j]のときcountに1を加えます。 countを返します。
def countInversions(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] > nums[j]:
count += 1
return countマージしながら数えるマージソート
考え方
リストを中央で分割します。転倒は、両方の値が左半分にあるか、両方が右半分にあるか、またはそれぞれが別々の側にあるかのいずれかです。それぞれの半分を再帰的に処理すると、最初の2種類を数え、その半分をソートします。ソートでは値は半分の内部でしか移動しないため、すべての左側の値は引き続きすべての右側の値より前にあり、左右にまたがるペアは変わりません。
マージでは、left[i] ≤ right[j]なら、left[i]を配置します。まだ待っている右側の値はすべてright[j]以上なので、転倒は生じません。そうでなければ、right[j]はleft[i]より小さく、左半分はソート済みなので、まだ待っているすべての左側の値よりも小さくなります。その個数を加算します。同値の場合に左側の値を先に配置すれば、等しい値同士が転倒に数えられることはありません。
[5, 3, 8, 1, 4]では、各半分に1個と2個の転倒があります。[3, 5]と[1, 4, 8]をマージすると、1は3と5を追い越し、4は5を追い越します。したがって、1 + 2 + 3 = 6です。
アルゴリズム
numsをコピーし、同じ長さのバッファを作ります。- 2 個未満の値の範囲をソートして数える場合は、0 を返します。
- それ以外の場合は、
midで分割し、それぞれの半分をソートして数えます。 - バッファを使って半分ずつマージします。
left[i] ≤ right[j]の場合は左の値を取り、そうでない場合は右の値を取り、まだ配置されていない左の値の個数を加算します。 - マージした範囲を元にコピーし、3 つのカウントの合計を返します。
def sortAndCount(a, buf, lo, hi):
# Sorts a[lo:hi] and returns the number of inversions inside it.
if hi - lo < 2:
return 0
mid = (lo + hi) // 2
count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
# Merge the two sorted halves, counting the pairs that cross the middle.
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
buf[k] = a[i]
i += 1
else:
# a[j] is smaller than every left value not placed yet: a[i..mid-1].
buf[k] = a[j]
j += 1
count += mid - i
k += 1
while i < mid:
buf[k] = a[i]
i += 1
k += 1
while j < hi:
buf[k] = a[j]
j += 1
k += 1
a[lo:hi] = buf[lo:hi]
return count
def countInversions(nums):
a = list(nums) # sort a copy, not the caller's list
return sortAndCount(a, [0] * len(a), 0, len(a))
落とし穴と境界ケース
- 右の値を配置したときに1を加算します。まだ待っている左の値をすべて追い越すため、その個数
mid - iを加算します。 - 同じ値のときに右の値を選び、左側の判定に
left[i] < right[j]を使っています。すると、[2, 2, 2, 1]では等しい2同士を比較してしまい、3より大きい値を返します。≤を使ってください。 - 片方の半分がなくなった後、残りをコピーしながら数えています。左側に残った値の後ろには右側の値がなく、右側に残った値はすでにすべての左側の値と比較されています。
よくある質問3
配列における反転とは何ですか？
転倒とは、i < jかつnums[i] > nums[j]となる位置のペアで、大きい値が小さい値より前にあります。ソート済みのリストの転倒数は0で、異なる値からなる逆順のリストでは最大のn(n-1)/2になります。この数は、バブルソートで行われる隣接要素の交換回数と等しくなります。
マージソートで転倒数を数える場合の時間計算量はどのくらいですか？
O(n log n)時間、マージバッファ用に追加のO(n)領域が必要です。マージの各log n段階では、すべての値に1回ずつアクセスします。2 × 10^4個の値の場合、約3 × 10^5ステップです。ペアごとに処理するループはO(n²)です。
マージソートを使わずに転倒数を数えることはできますか？
はい。値の順位を対象とするFenwick tree（二分インデックス木）は、リストを1回走査し、各値について、それより前にある値のうち大きいものがいくつあるかを、値ごとにO(log n)で求めます。合計でもO(n log n)です。部分木のサイズを追跡する平衡二分探索木でも同じように機能します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countInversions(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [5, 3, 8, 1, 4]
期待される出力
6