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à count(arr) = 3.
Cho arr = [4, 6, 2, 9], output là count(arr) = 2.
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
By Liliana
def count(arr):
n=len(arr)
if n<2:
return 0
left=arr[:n//2]
right=arr[n//2:]
kq=0
kq+=count(left)
kq+=countI(right)
i=0
j=0
k=0
while i<len(left) and j<len(right):
if left[i]<=right[j]:
arr[k]=left[i]
i+=1
k+=1
else:
arr[k]=right[j]
j+=1
k+=1
kq+=len(left)-i
if i<len(left):
arr[k:]=left[i:]
if j<len(right):
arr[k:]=right[j:]
return kq