Cho A[1…n] là một mảng chứa n số khác nhau. Nếu i < j và A[i] > A[j] thì cặp số (i, j) được gọi là một “nghịch đảo”. VÍ dụ mảng (2, 3, 8, 6, 1) có 5 “nghịch đảo”.Viết chương trình tìm số nghịch đảo của mảng A[1…n] sao cho độ phức tạp của thuật toán là O(nlogn).
Thực sự đã quá bí về bài này 
, cần mọi người giúp đỡ
Dùng tư tưởng chia để trị giống như merge sort:
bước quan trọng nhất ở đây là phần trộn hai mảng left và right, khi trộn số cặp nghịch đảo có được chính là tổng số các số bé hơn của mảng right so với mảng left hay = sum count(right[j]<left[i]) (1)
Vì các bước này tương tự merge sort nên chỉ cần thêm bước đếm biểu thức (1) khi mà right[j] <left[i] trong bước trộn của sắp xếp trộn. Khi mà dãy left,right đã được sắp xếp thì việc (1) = sum(len(left)-i) chính là việc đếm số lớn hơn right[j] trong dãy left đó cũng chính là kết quả bài toán
Code tham khảo:
def count(a):
n=len(a)
if n<2:
return 0
left=a[:n//2]
right=a[n//2:]
ans=0
ans+=count(left)
ans+=count(right)
i=0
j=0
k=0
while i<len(left) and j<len(right):
if left[i]<=right[j]:
a[k]=left[i]
i+=1
k+=1
else:
a[k]=right[j]
j+=1
k+=1
ans+=len(left)-i
if i<len(left):
a[k:]=left[i:]
if j<len(right):
a[k:]=right[j:]
return ans
print count([2,3,8,6,1])
hehe bài này giống y như bài đếm số lượng swap trong insertion sort 
Ngoài cach dùng Merge Sort ra thì cũng còn 1 cách nữa
Đó là dùng Fenwick Tree a.k.a Binary Indexed Tree, đây là một bài là ứng dụng cơ bản và áp dụng code BIT thuần túy vào luôn, nên nếu bạn đã học BIT rồi chắc chắn sẽ không cần phải hỏi, và ngược lại đã hỏi thì chưa biết, mình chỉ reply để nếu ai muốn tìm hiểu thêm thì có thể coi thử nó là cái gì. Chứ như đã nói, đọ hack não của nó là ghê hơn rất nhiều so với Merge nên nếu chưa biết thì dùng Merge an toàn hơn.
đây là lệnh gì anh. Em chưa rành Python lắm:
left=a[:n//2]
right=a[n//2:]
chạy thử: https://www.hackerrank.com/challenges/insertion-sort
giải thích cách vừa merge vừa đếm số lượng swap: https://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf
O(N^2) nhé.
Link die rồi bạn.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?