Tìm số cặp chưa được sắp xếp trong một mảng

Question

Tôi gặp sự cố thuật toán thú vị:

Cho số lượng cặp không được sắp xếp trong mảng đó, cho biết {1, 3, 2 }, câu trả lời là 1 vì {3, 2} không được đặt hàng và đối với mảng {3, 2, 1}, câu trả lời là 3 vì {3, 2}, {3, 1}, {2, 1} .

Rõ ràng, điều này có thể được giải quyết bằng vũ lực với thời gian chạy O (n^2) hoặc hoán đổi tất cả các cặp có thể sau đó loại bỏ các cặp không hợp lệ đó.

Câu hỏi của tôi là cơ thể nào có bất kỳ giải pháp nào tốt hơn và bạn sẽ làm như thế nào vì nó có vẻ như là một vấn đề lập trình động. Đoạn mã sẽ hữu ích

Answer 1

Có thể giải quyết vấn đề này trong thời gian O(n log n) bằng cách sử dụng cây tìm kiếm nhị phân cân bằng. Đây là mã giả của thuật toán này:

tree = an empty balanced binary search tree 
answer = 0 
for each element in the array: 
    answer += number of the elements in the tree greater then this element 
    add this element to the tree 

Answer 2

Bạn có thể sử dụng thuật toán sắp xếp hợp nhất đã sửa đổi. Hợp nhất sẽ giống như thế này.

merge(a, b): 
    i = 0 
    j = 0 
    c = new int[a.length+b.length] 
    inversions = 0 
    for(k = 0 ; k < Math.min(a.length, b.length); k++) 
     if(a[i] > b[j]): 
      inversions++ 
      c[k] = b[j] 
      j++ 
     else: 
      c[k] = a[i] 
      i++ 
    //dump the rest of the longer array in c 
    return inversions 

Hợp nhất được thực hiện trong thời gian O (n). Độ phức tạp thời gian của toàn bộ sắp xếp hợp nhất là O (n log n)

Answer 3

Bạn có thể sử dụng phiên bản hợp nhất đã sửa đổi để đếm số lần đảo ngược. Bí quyết là trong khi sáp nhập hai mảng phụ được sắp xếp, bạn có thể biết các yếu tố không đúng chỗ. Nếu có bất kỳ phần tử nào trong phần con bên phải cần phải đi trước các phần tử trong phần con bên trái, chúng là các phần tử đảo ngược. Tôi đã viết mã cho điều này trong python. Bạn có thể kiểm tra giải thích dưới đây để hiểu rõ hơn. Nếu bạn không thể hiểu được sắp xếp hợp nhất, tôi khuyên bạn nên revist sắp xếp hợp nhất sau đó điều này sẽ được trực quan.

def merge_sort(l): 
    if len(l) <= 1: 
     return (0, l) 
    else: 
     mid = len(l)/2 
     count_left, ll = merge_sort(l[0:mid]) 
     count_right, lr = merge_sort(l[mid:]) 
     count_merge, merged = merge(ll, lr) 
     total = count_left + count_right + count_merge 
     return total, merged 

def merge(left, right): 
    li, ri = 0, 0 
    merged = []   
    count = 0 
    while li < len(left) and ri < len(right): 
     if left[li] < right[ri]: 
      merged.append(left[li]) 
      li += 1 
     else: 
      count += 1 
      merged.append(right[ri]) 
      ri += 1 

    if li < len(left): 
     merged.extend(left[li:]) 
    elif ri < len(right): 
     merged.extend(right[ri:]) 
    return count, merged 

if __name__ == '__main__': 
    # example 
    l = [6, 1 , 2, 3, 4, 5] 
    print 'inverse pair count is %s'%merge_sort(l)[0] 

• Merge sort chạy trong n * log (n) thời gian.
• cho danh sách được chuyển l, merge_sort trả về một bộ (theo dạng (inversion_count, list)) của số nghịch đảo và danh sách được sắp xếp
• Bước phối đếm đếm số nghịch đảo và lưu nó trong số biến.