die Anzahl der ungeordneten Paar in einem Array

Question

ich zu einem interessanten Algorithmus Problem lautete:

ein Array von Integer-Gegeben, finden die Anzahl der ungeordneten Paare in diesem Array, sagen gegeben {1, 3, 2 }, die Antwort ist 1, weil {3, 2} nicht geordnet ist, und für Array {3, 2, 1} lautet die Antwort 3, weil {3, 2}, {3, 1}, {2, 1} .

Offensichtlich kann dies durch Brute Force mit O (n^2) Laufzeit gelöst werden, oder alle möglichen Paare permutieren und diese ungültigen Paare dann beseitigen.

Meine Frage ist, hat jeder Körper eine bessere Lösung und wie würden Sie es tun, weil es wie ein dynamisches Programmierproblem scheint. Ein Code-Schnipsel wäre hilfreich

Answer 1

Es ist möglich, dieses Problem in O(n log n) Zeit mit einem ausgewogenen binären Suchbaum zu lösen. Hier ist ein Pseudo-Code dieses Algorithmus:

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

Sie können einen Merge-Sort-Algorithmus modifiziert verwenden. Das Zusammenführen würde ungefähr so ​​aussehen.

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 

Das Zusammenführen erfolgt in O (n) Zeit. Die Zeitkomplexität der gesamten Zusammenführungssortierung ist O (n log n)

Answer 3

Sie können eine geänderte Version von merge sort verwenden, um die Anzahl der Inversionen zu zählen. Der Trick besteht darin, dass Sie beim Zusammenführen von zwei sortierten Sub-Arrays die Elemente kennen lernen, die fehl am Platz sind. Wenn Elemente im rechten Subarray vorhanden sind, die vor denen im linken Subarray stehen müssen, sind sie die invertierten. Ich habe den Code dafür in Python geschrieben. Sie können die Erklärung darunter zum besseren Verständnis überprüfen. Wenn Sie Merge Sort nicht verstehen können, empfehle ich Ihnen, merge sort zu revidieren, nach dem dies intuitiv wäre.

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 läuft in n * log (n) Zeit.
• für die übergebene Liste l, merge_sort ein Tupel zurück (in Form von (inversion_count, list)) der Anzahl von Umkehrungen und der sortierten Liste
• Merge Schritt zählt die Anzahl von Inversionen und speichert ihn in der Variable Zählung.