Ottieni la distanza di elementi all'interno di un array?

Question

Sto lottando con un compito piuttosto semplice che ha una matrice di numeri interi non negativi in ​​cui ho bisogno di restituire la distanza più vicina.

Array: arr = [8, 24, 3, 20, 1, 17]

Soluzione: 2, arr[2]-arr[4]

Sor lontano, sono riuscito solo a dare una soluzione di O (n^2), che ovviamente non è abbastanza buono:

def smallest_distance(a) 
    result = nil 
    a.each_with_index do |item1, index1| 
    a.each_with_index do |item2, index2| 
     next if index1 == index2 
     temp = (item1 - item2) >= 0 ? item1 - item2 : item2 - item1 
     result = temp if result.nil? || temp < result 
    end 
    end 
    result 
end 

Qualche idea su come migliorare questo?

Answer 1

La soluzione è ordinare l'array e quindi iterarlo. Ora devi solo verificare i candidati adiacenti allo (arr[i],arr[i+1]) e non ogni coppia di elementi.

Questo funziona in O(NlogN).

Si noti che questa è una generalizzazione di Element Distinctness Problem, quindi se si è interessati alle prestazioni del caso peggiore, non è possibile ottenere risultati migliori di O(NlogN).

Answer 2

La soluzione che viene pubblicata correttamente è il tempo n*log(n), che è il tempo più veloce per il quale è possibile trovare una soluzione. Il codice rubino per la sua soluzione sembrerà qualcosa di simile:

def smallest_distance(a) 
    sorted = array.sort 
    shortest = 999999 # arbitrary large value 
    for i in 0..sorted.length 
    comparison = sorted[i+1] - sorted[i] if sorted[i+1] != nil 
    if comparison < shortest 
     shortest = comparison 
    end 
    end 
    return shortest 
end 

Answer 3

In genere per questo tipo di problema relativo all'array. Se si dispone di algoritmo uguale o peggiore di O (n^2), è sempre possibile considerare l'utilizzo di un algoritmo di ordinamento per elaborarlo. Di solito prende O (lgn), quindi potresti avere un algoritmo lineare dopo.

Per questo problema, è possibile ordinare questo array. Quindi confronta solo gli elementi adiacenti per un ciclo. La complessità del tempo del risultato finale è O (n logn) che è migliore della tua idea originale.

in modo da poter:

sorted = arr.sort 

Quindi utilizzare un ciclo per copmare

arr[i] with ar[i+1] from i = 0 ~ len-1