Count Inversions
Cho một mảng các số nguyên arr, một nghịch thế trong dãy là một cặp số u, v thỏa mãn: u < v và a[u] > a[v]. Bạn hãy viết hàm đếm số nghịch thế trong mảng arr.
Ví dụ:
- Cho
arr = [3, 2, 1], output làcountInversions(arr) = 3. - Cho
arr = [4, 6, 2, 9], output làcountInversions(arr) = 2.
Đầu vào/Đầu ra
-
[Giới hạn thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS và Go
- [Đầu vào] Array of integers arr
1 <= arr.size <= 10000
0 <= arr[i] <= 10000 -
[Đầu ra] Integer
Post Comment