Trovare il numero di coppia non ordinata in una matrice

Question

mi sono imbattuto in un interessante problema algoritmo:

Dato un array di numeri interi, trovare il numero di coppie non ordinate in tale matrice, dire dato {1, 3, 2 }, la risposta è 1 perché {3, 2} non è ordinato e per matrice {3, 2, 1}, la risposta è 3 perché {3, 2}, {3, 1}, {2, 1} .

Ovviamente, questo può essere risolto con la forza bruta con O (n^2) tempo di esecuzione, o permuta tutte le coppie possibili quindi eliminare quelle coppie non valide.

La mia domanda è: qualsiasi organismo ha una soluzione migliore e come lo faresti perché sembra un problema di programmazione dinamica. Uno snippet di codice sarebbe utile

Answer 1

È possibile risolvere questo problema nel tempo O(n log n) utilizzando un albero di ricerca binario bilanciato. Ecco una pseudo-codice di questo algoritmo:

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

è possibile utilizzare un algoritmo di merge-sort modificato. La fusione sarebbe simile a questa.

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 

L'unione viene eseguita nel tempo O (n). La complessità temporale dell'intero ordinamento di unione è O (n log n)

Answer 3

È possibile utilizzare una versione modificata di unisci sort per contare il numero di inversioni. Il trucco è che mentre si uniscono due sottoarray ordinati si può arrivare a conoscere gli elementi che sono fuori luogo. Se ci sono elementi nel sottoarray di destra che devono andare prima di quelli nel subarray di sinistra, sono quelli invertiti. Ho scritto il codice per questo in python. Puoi controllare la spiegazione qui sotto per una migliore comprensione. Se non si è in grado di capire l'unire sort, suggerirei di revisare l'unisci merge dopo il quale ciò sarebbe intuitivo.

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 viene eseguito in n * log (n).
• per la lista l passato, merge_sort restituisce una tupla (in forma di (inversion_count, lista)) del numero di inversioni e la lista ordinata
• passo Unisci conta il numero di inversioni e lo memorizza nel conteggio variabile.