forked from Gitlink/forgeplus
34 lines
726 B
Python
34 lines
726 B
Python
def inverse_ordinal_numbers(arr):
|
|
n = len(arr)
|
|
if n <= 1:
|
|
return 0, arr
|
|
|
|
mid = n // 2
|
|
|
|
inverse_l, arr_l = inverse_ordinal_numbers(arr[:mid])
|
|
inverse_r, arr_r = inverse_ordinal_numbers(arr[mid:])
|
|
|
|
nl, nr = len(arr_l), len(arr_r)
|
|
|
|
arr_l.append(9223372036854775807)
|
|
arr_r.append(9223372036854775807)
|
|
|
|
i, j = 0, 0
|
|
new_arr = []
|
|
|
|
inverse = inverse_l + inverse_r
|
|
|
|
while i < nl or j < nr:
|
|
if arr_l[i] <= arr_r[j]:
|
|
inverse += j
|
|
new_arr.append(arr_l[i])
|
|
i += 1
|
|
else:
|
|
new_arr.append(arr_r[j])
|
|
j += 1
|
|
return inverse, new_arr
|
|
|
|
|
|
a = [1, 2, 3, 4, 5, 6, 5, 7, 8, 2, 9, 1]
|
|
print(inverse_ordinal_numbers(a))
|