Python-Algorithmus – Finden Sie schnell zwei Zahlen, die die Bedingungen erfüllen-Python-Tutorial-php.cn

Python-Algorithmus – Finden Sie schnell zwei Zahlen, die die Bedingungen erfüllen

高洛峰

Freigeben： 2016-10-18 10:38:23

Original

2186 Leute haben es durchsucht

Die Prämisse der Frage ist, dass es zwei solcher Zahlen geben muss

Ich werde die Lösung nicht aufschreiben... Sie können sich das nicht vorstellen.

Die erste Was mir einfiel, war die Hash-Tabelle am Ende von Lösung zwei

(Eigentlich dachte ich daran, ein Array so groß wie das Ziel zu erstellen. Wenn es existiert, schreiben Sie den Index, aber wenn Sie sie finden möchten Alles in allem braucht man ein zweidimensionales Array. Aber wenn das Ziel sehr groß ist, ist es dann Platzverschwendung? Okay... also habe ich es in Dict geändert.

Für die Frage waren nur zwei Zahlen erforderlich - -

Erweiterte Fragen sind interessanter

Finde drei. Es sollte nicht schwierig sein, aber bei anderen Dingen bin ich mir nicht sicher, ich würde gerne mehr hinzufügen ...

1. Zweidimensionales Array

def find_pair(A, target):
    B = [[] for i in range(target + 1)]
    for i in range(0, len(A)):
        if A[i] <= target:
            B[A[i]].append(i)
    for i in range(0, target / 2 + 1):
        if len(B[i]) != 0 and len(B[target - i]) != 0:
            print(i, B[i], target-i, B[target-i])
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

Nach dem Login kopieren

2. Diese Methode wurde nicht neu sortiert Ich weiß, was die Rückgabe des Index im Buch bedeutet ... Ich bin faul und verwende einfach den integrierten Index ...

def find_pair(A, target):
    B = {}
    for i in range(0, len(A)):
        if A[i] <= target:
            if not B.has_key(A[i]):
                B[A[i]] = [i]
            else:
                B[A[i]].append(i)
    for i in range(0, target / 2 + 1):
        if B.has_key(i) and B.has_key(target-i):
            print(i, B[i], target-i, B[target-i])
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

Nach dem Login kopieren

def find_pair(A, target):
    A.sort()
    i, j = 0, len(A) - 1
    while i < j:
        s = A[i] + A[j]
        if s == target:
            print(i, A[i], j, A[j])
            i += 1
            j -= 1
        elif s < target:
            i += 1
        else:
            j -= 1
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

Nach dem Login kopieren