-
Notifications
You must be signed in to change notification settings - Fork 39
/
solution_44.py
31 lines (24 loc) · 1.11 KB
/
solution_44.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def coding_problem_44(arr):
"""
We can determine how "out of order" an array A is by counting the number of inversions it has. Two elements A[i]
and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.
Given an array, count the number of inversions it has. Do this faster than O(N^2) time.
You may assume each element in the array is distinct.
Examples:
>>> coding_problem_44([1, 2, 3, 4, 5])
0
>>> coding_problem_44([2, 4, 1, 3, 5]) # inversions: (2, 1), (4, 1), (4, 3)
3
>>> coding_problem_44([5, 4, 3, 2, 1]) # every distinct pair forms an inversion
10
Note: complexity is that of sorting O(n log(n)) plus a linear pass O(n), therefore bounded by O(n log(n))
"""
sorted_indexes = sorted(range(len(arr)), key=lambda x: arr[x])
inversions = 0
while sorted_indexes:
inversions += sorted_indexes[0]
sorted_indexes = [si - 1 if si > sorted_indexes[0] else si for si in sorted_indexes[1:]]
return inversions
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=True)