समस्या
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
उदाहरण
इनपुट:
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.
इनपुट:
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
जब merge करते समय left-side का number right-side के number से बड़ा रह जाए, तब inversion count होती है.
संकेत 2
List को recursively split करें और sorted halves को merge करते समय cross-pairs count करें.
संकेत 3
Duplicates का ध्यान रखें: equal values inversions नहीं होतीं, इसलिए comparison direction important है.
अपेक्षित जटिलता
समय O(n log n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।