Suche Paare von Elementen in Integer-Array, so dass abs (v [i] -v [j]) minimiert

Question

Können sagen wir int-Array mit 5 Elementen aufweisen: 1, 2, 3, 4, 5

Was ich tun muss, ist mindestens abs Wert von Arrays Elemente Subtraktion zu finden:

Wir möchten, dass

1-2 2-3 3-4 4-5 

1-3 2-4 3-5 

1-4 2-5 

1-5 

überprüfen müssen und minimalen abs Wert dieser Subtraktionen finden. Wir können es mit 2 for s finden. Die Frage ist, gibt es einen Algorithmus für die Suche nach Wert mit nur for?

Answer 1

sortieren die Liste und subtrahieren nächsten zwei Elemente

Answer 2

Nein, es sei denn, Sie die Liste wissen sortiert ist, müssen Sie zwei

Answer 3

Seine einfache Iterate in einer for-Schleife

 keep 2 variable "minpos and maxpos " and " minneg" and "maxneg" 
     check for the sign of the value you encounter and store maximum positive in maxpos 
     and minimum +ve number in "minpos" do the same by checking in if case for number 
     less than zero. Now take the difference of maxpos-minpos in one variable and 
     maxneg and minneg in one variable and print the larger of the two . You will get 
     desired. 

I you definitely know how to find max and min in one for loop glauben

Answer 4

Das Problem ist gleich Sortin G. Jeder Sortieralgorithmus könnte verwendet werden und am Ende die Differenz zwischen den nächsten Elementen zurückgeben. Ein letzter Durchlauf über die Daten könnte verwendet werden, um diesen Unterschied zu finden, oder er könnte während der Sortierung beibehalten werden. Bevor die Daten sortiert werden, ist die minimale Differenz zwischen benachbarten Elementen eine obere Grenze.

Verwenden Sie also einen Sortieralgorithmus ohne zwei Schleifen, um dies ohne zwei Schleifen zu tun. In gewisser Weise fühlt es sich an wie Semantik, aber rekursive Sortieralgorithmen werden es mit nur einer Schleife tun. Wenn dieses Problem die n (n + 1)/2-Subtraktionen ist, die für den einfachen Fall mit zwei Schleifen erforderlich sind, können Sie einen O (n log n) -Algorithmus verwenden.

Answer 5

Die nachweisbar beste Lösung ist assymptotisch linear O (n) bis zu konstanten Faktoren. Dies bedeutet, dass die benötigte Zeit proportional zur Anzahl der Elemente im Array ist (was natürlich das Beste ist, was wir tun können, da wir zumindest jedes Element des Arrays lesen müssen, das bereits O (n.) benötigt) Zeit).

ist hier eine solche O (n) Lösung (die auch O (1) Raum verwendet, wenn die Liste kann in-place geändert werden):

int mindiff(const vector<int>& v) 
{ 
    IntRadixSort(v.begin(), v.end()); 

    int best = MAX_INT; 

    for (int i = 0; i < v.size()-1; i++) 
    { 
     int diff = abs(v[i]-v[i+1]); 
     if (diff < best) 
      best = diff; 
    } 

    return best; 
} 

IntRadixSort einer linearen Zeit ist fester Breite integer Sortier Algorithmus definiert hier:

http://en.wikipedia.org/wiki/Radix_sort

Das Konzept ist, dass Sie die Fest Bitbreite Natur ints nutzen, indem sie in einer Reihe von festen Pässe auf den Bit-Positionen partitionieren. dh partitioniere sie auf dem hi-Bit (32nd), dann auf dem nächsthöheren (31.), dann auf dem nächsten (30.) und so weiter - was nur lineare Zeit benötigt.

Answer 6

Das könnte Sie werden helfen:

end=4; 
subtractmin; 
m=0; 
for(i=1;i<end;i++){ 
if(abs(a[m]-a[i+m])<subtractmin) 
subtractmin=abs(a[m]-a[i+m];} 
if(m<4){ 
m=m+1 
end=end-1; 
i=m+2; 
}}