Đề bài
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.
Ràng buộc
0 ≤ length ≤ 200,000
Ví dụ
Đầu vào:
numbers = [2, 4, 1, 3, 5]
Kết quả mong đợi:
expected = 3Đầu vào:
std::vector<long long> numbers = {2, 4, 1, 3, 5};
Kết quả mong đợi:
long long expected = 3;Đầu vào:
long[] numbers = new long[] {2, 4, 1, 3, 5};
Kết quả mong đợi:
long expected = 3;Giải thích
Out-of-order pairs: (2,1), (4,1), (4,3): 3 inversions.
Đầu vào:
numbers = [1, 2, 3]
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<long long> numbers = {1, 2, 3};
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[] numbers = new long[] {1, 2, 3};
Kết quả mong đợi:
long expected = 0;Giải thích
Already sorted: 0 inversions.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Một nghịch thế được tính khi một số ở nửa trái vẫn lớn hơn một số ở nửa phải trong lúc trộn.
Gợi ý 2
Chia danh sách đệ quy và đếm các cặp chéo trong khi merge hai nửa đã được sắp xếp.
Gợi ý 3
Cẩn thận với phần tử trùng nhau: các giá trị bằng nhau không phải là nghịch thế, nên hướng so sánh rất quan trọng.
Độ phức tạp mong đợi
thời gian O(n log n), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.