難しい 1件解決済み 正答率100.0%

Count Inversions

Count the out-of-order pairs in a list.

このチャレンジで学べること

  • マージしながら順序が逆の組を数える
  • マージソートにカウントを追加する
  • O(n²) から O(n log n) に改善する

問題

An inversion is a pair of positions i < j with numbers[i] > numbers[j]. Count all inversions. Lists can be long, so a merge-sort based O(n log n) count is needed.

Implement count_inversions(numbers).

Input

numbers: The list of integers.

Output

Return the number of inversions.

制約

0 ≤ length ≤ 200,000

例

例 1
入力:
numbers = [2, 4, 1, 3, 5]

期待される出力:
expected = 3
入力:
std::vector<long long> numbers = {2, 4, 1, 3, 5};

期待される出力:
long long expected = 3;
入力:
long[] numbers = new long[] {2, 4, 1, 3, 5};

期待される出力:
long expected = 3;

解説

Out-of-order pairs: (2,1), (4,1), (4,3): 3 inversions.

例 2
入力:
numbers = [1, 2, 3]

期待される出力:
expected = 0
入力:
std::vector<long long> numbers = {1, 2, 3};

期待される出力:
long long expected = 0;
入力:
long[] numbers = new long[] {1, 2, 3};

期待される出力:
long expected = 0;

解説

Already sorted: 0 inversions.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

反転は、マージ中に左側の数が右側の数より大きいときに数えます。

ヒント 2

再帰的に分割し、ソート済みの半分をマージしながら交差する組を数えます。

ヒント 3

重複値に注意します。等しい値は反転ではないので、比較の向きが重要です。

目安の計算量

時間 O(n log n)、追加メモリ O(n)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 970 ms - 5/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。