Suchen der beiden nächsten Zahlen in einer Liste mit Sortierung

Question

Wenn ich eine Liste von Ganzzahlen/Gleitkommazahlen gegeben wird, wie würde ich die beiden nächsten Zahlen mit Sortierung finden?

Answer 1

Ein solches Verfahren wird tun, was Sie wollen:

>>> def minDistance(lst): 
    lst = sorted(lst) 
    index = -1 
    distance = max(lst) - min(lst) 
    for i in range(len(lst)-1): 
     if lst[i+1] - lst[i] < distance: 
      distance = lst[i+1] - lst[i] 
      index = i 
    for i in range(len(lst)-1): 
     if lst[i+1] - lst[i] == distance: 
      print lst[i],lst[i+1] 

Im ersten for Schleife wir den Mindestabstand zu erfahren, und in der zweiten Schleife, wir drucken alle Paare mit diesem Abstand. Funktioniert wie folgt:

>>> lst = (1,2,3,6,12,9,1.4,145,12,83,53,12,3.4,2,7.5) 
>>> minDistance(lst) 
2 2 
12 12 
12 12 
>>> 

Answer 2

Es könnte mehr als eine Möglichkeit sein. Betrachten Sie diese Liste

[0,1, 20, 25, 30, 200, 201] 

[0,1] und [200, 201] sind gleich am nächsten.

Answer 3

Jose hat einen gültigen Punkt. Sie können diese Fälle jedoch als gleich betrachten und sich nicht darum kümmern, das eine oder das andere zurückzugeben.

Ich glaube nicht, dass Sie einen Sortieralgorithmus benötigen, pro sagen, aber vielleicht nur eine Art ‚Champion‘ Algorithmus wie diese:

def smallestDistance(self, arr): 
    championI = -1 
    championJ = -1 
    champDistance = sys.maxint 
    i = 0 
    while i < arr.length: 
     j = i + 1 
     while j < arr.length: 
      if math.fabs(arr[i] - arr[j]) < champDistance: 
       championI = i 
       championJ = j 
       champDistance = math.fabs(arr[i] - arr[j]) 
      j += 1 
     i += 1 
    r = [arr[championI], arr[championJ]] 
    return r 

Diese Funktion wird eine Sub-Array mit den beiden Werten zurückkehren das sind am nächsten zusammen. Beachten Sie, dass dies nur bei einem Array von mindestens zwei Long funktioniert. Andernfalls werden Sie einen Fehler werfen.

Ich denke, der beliebte Sortieralgorithmus wie Blasensortierung würde das recht gut tun. Obwohl es bei O(n^2) Zeit möglich ist, wenn diese Art von Sache für Sie von Bedeutung ist ...

Hier ist Standard Blasensortieren basierend auf der Sortierung von Arrays durch ganzzahlige Größe.

def bubblesort(A): 
    for i in range(len(A)): 
    for k in range(len(A) - 1, i, -1): 
     if (A[k] < A[k - 1]): 
     swap(A, k, k - 1) 

def swap(A, x, y): 
    tmp = A[x] 
    A[x] = A[y] 
    A[y] = tmp 

Sie können den Algorithmus nur leicht an Ihre Zwecke anpassen, wenn Sie darauf bestehen, einen Sortieralgorithmus zu verwenden. Ich denke jedoch, die ursprüngliche Funktion funktioniert auch ...

hoffe, dass hilft.