Holen Sie sich die zweitgrößte Zahl in einer Liste in linearer Zeit
Ich lerne Python und die einfache Handhabung von Listen wird als Vorteil dargestellt. Manchmal ist es so, aber schau dir das an:
>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> numbers.remove(max(numbers))
>>> max(numbers)
74
Eine sehr einfache und schnelle Möglichkeit, die zweitgrößte Nummer aus einer Liste zu erhalten. Die einfache Listenverarbeitung hilft dabei, ein Programm zu schreiben, das zweimal durch die Liste läuft, um das größte und dann das zweitgrößte zu finden. Es ist auch zerstörerisch - ich brauche zwei Kopien der Daten, wenn ich das Original behalten wollte. Wir brauchen:
>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> if numbers[0]>numbers[1]):
... m, m2 = numbers[0], numbers[1]
... else:
... m, m2 = numbers[1], numbers[0]
...
>>> for x in numbers[2:]:
... if x>m2:
... if x>m:
... m2, m = m, x
... else:
... m2 = x
...
>>> m2
74
Die Liste läuft nur einmal durch, ist aber nicht so knapp und klar wie bei der vorherigen Lösung.
Also: Gibt es in beiden Fällen einen Weg, beides zu haben? Die Klarheit der ersten Version, aber der Single-Durchlauf der zweiten Version?
Da @OscarLopez und ich unterschiedliche Meinungen darüber haben, was das zweitgrößte bedeutet, gebe ich den Code gemäß meiner Vision und im Einklang mit dem ersten Algorithmus, der vom Fragesteller bereitgestellt wird.
def second_largest(numbers):
count = 0
m1 = m2 = float('-inf')
for x in numbers:
count += 1
if x > m2:
if x >= m1:
m1, m2 = x, m1
else:
m2 = x
return m2 if count >= 2 else None
(Hinweis: Negative Unendlichkeit wird hier anstelle von None verwendet, da None in Python 2 und 3 unterschiedliches Sortierverhalten hat - siehe Python - Finde die kleinste Anzahl ; eine Überprüfung der Anzahl der Elemente in numbers stellt sicher, dass die negative Unendlichkeit gewonnen wird Wird nicht zurückgegeben, wenn die tatsächliche Antwort nicht definiert ist.)
Wenn das Maximum mehrfach auftritt, kann es auch das zweitgrößte sein. Ein weiterer Aspekt dieses Ansatzes ist, dass er korrekt funktioniert, wenn weniger als zwei Elemente vorhanden sind. dann gibt es keinen zweitgrößten.
Ausführen der gleichen Tests:
second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 2
second_largest([10,7,10])
=> 10
second_largest([1,1,1,1,1,1])
=> 1
second_largest([1])
=> None
second_largest([])
=> None
Update
Ich habe die Bedingungen neu strukturiert, um die Leistung drastisch zu verbessern. fast zu 100% in meinen Tests auf Zufallszahlen. Der Grund dafür ist, dass in der Originalversion die Variable Elif immer in dem wahrscheinlichen Fall ausgewertet wurde, dass die nächste Zahl nicht die größte in der Liste ist. Mit anderen Worten, für praktisch jede Zahl in der Liste wurden zwei Vergleiche durchgeführt, wohingegen ein Vergleich meistens ausreicht - wenn die Zahl nicht größer als die zweitgrößte ist, ist sie auch nicht größer als die größte.
Sie können das Modul heapq verwenden:
>>> el = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> import heapq
>>> heapq.nlargest(2, el)
[90.8, 74]
Und geh von dort ...
Sie können immer sorted verwenden.
>>> sorted(numbers)[-2]
74
Versuchen Sie die Lösung unten, es ist O(n), und es wird die zweitgrößte Zahl in der Variable second gespeichert und zurückgegeben. Beachten Sie, dass, wenn alle Elemente in numbers gleich sind oder wenn numbers leer ist oder wenn sie ein einzelnes Element enthalten, die Variable second den Wert None erhält. Dies ist richtig, da in diesen Fällen kein "zweiter" steht größtes "Element.
Achtung : Hier wird der Wert des "zweiten Maximums" ermittelt. Wenn es mehr als einen Wert gibt, der "erstes Maximum" ist, werden sie alle als das gleiche Maximum behandelt - in meiner Definition in einer Liste wie der folgenden: [10, 7, 10] Die richtige Antwort ist 7.
def second_largest(numbers):
first, second = None, None
for n in numbers:
if n > first:
first, second = n, first
Elif first > n > second:
second = n
return second
Hier sind einige Tests:
second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 1
second_largest([10, 7, 10])
=> 7
second_largest([1,1,1,1,1,1])
=> None
second_largest([1])
=> None
second_largest([])
=> None
>>> l = [19, 1, 2, 3, 4, 20, 20]
>>> sorted(set(l))[-2]
19
Der quickselect-Algorithmus , O(n) Cousin to quicksort wird das tun, was Sie wollen. Quickselect hat eine durchschnittliche Leistung von O (n). Die Leistung im ungünstigsten Fall ist wie bei quicksort O (n ^ 2). Dies ist jedoch selten, und Änderungen an der Schnellauswahl reduzieren die Leistung im ungünstigsten Fall auf O (n).
Die Idee von Quickselect besteht darin, den gleichen Drehpunkt, die niedrigere, höhere Idee von Quicksort zu verwenden, aber dann den unteren Teil zu ignorieren und nur den höheren Teil weiter zu ordnen.
Warum das Szenario komplizieren? Es ist sehr einfach und unkompliziert
- Liste in Set umwandeln - entfernt Duplikate
- Set wieder in Liste umwandeln - Liste in aufsteigender Reihenfolge
Hier ist ein Code
mlist = [2, 3, 6, 6, 5]
mlist = list(set(mlist))
print mlist[-2]
Wenn Sie nichts dagegen haben, numpy (import numpy as np) zu verwenden:
np.partition(numbers, -2)[-2]
gibt Ihnen das zweitgrößte Element der Liste mit einem garantierten Worst-Case O(n) Laufzeit .
Die partition(a, kth)-Methoden geben ein Array zurück, bei dem das kth-Element das gleiche ist wie in einem sortierten Array, alle vorherigen Elemente sind kleiner und alle dahinter liegenden Elemente sind größer.
hier gibt es einige gute Antworten für den Typ ([]), falls jemand dasselbe auf einen Typ ({}) benötigt, hier ist es,
def secondLargest(D):
def second_largest(L):
if(len(L)<2):
raise Exception("Second_Of_One")
KFL=None #KeyForLargest
KFS=None #KeyForSecondLargest
n = 0
for k in L:
if(KFL == None or k>=L[KFL]):
KFS = KFL
KFL = n
Elif(KFS == None or k>=L[KFS]):
KFS = n
n+=1
return (KFS)
KFL=None #KeyForLargest
KFS=None #KeyForSecondLargest
if(len(D)<2):
raise Exception("Second_Of_One")
if(type(D)!=type({})):
if(type(D)==type([])):
return(second_largest(D))
else:
raise Exception("TypeError")
else:
for k in D:
if(KFL == None or D[k]>=D[KFL]):
KFS = KFL
KFL = k
Elif(KFS == None or D[k] >= D[KFS]):
KFS = k
return(KFS)
a = {'one':1 , 'two': 2 , 'thirty':30}
b = [30,1,2]
print(a[secondLargest(a)])
print(b[secondLargest(b)])
Nur zum Spaß habe ich versucht, es xD benutzerfreundlich zu machen
O (n): Zeitkomplexität einer Schleife wird als O(n) betrachtet, wenn die Schleifenvariablen um einen konstanten Betrag inkrementiert/dekrementiert werden. Zum Beispiel haben folgende Funktionen O(n) Zeitkomplexität.
// Here c is a positive integer constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
Um die zweitgrößte Zahl zu finden, habe ich zuerst die größte Zahl ausfindig gemacht und dann die Liste durchsucht, wenn diese dort ist oder nicht
x = [1,2,3]
A = list(map(int, x))
y = max(A)
k1 = list()
for values in range(len(A)):
if y !=A[values]:
k.append(A[values])
z = max(k1)
print z
Dies kann in der Zeit [N + log (N) - 2] erfolgen, was etwas besser ist als die lockere obere Grenze von 2N (was auch an O(N)) denkbar ist.
Der Trick besteht darin, binäre rekursive Aufrufe und einen "Tennisturnier" -Algorithmus zu verwenden. Der Gewinner (die größte Anzahl) wird nach allen "Matches" (N-1-Zeit) ermittelt. Wenn wir jedoch die "Spieler" aller Matches aufzeichnen und unter ihnen alle Spieler zusammenfassen, die der Gewinner besiegt hat, Die zweitgrößte Zahl wird die größte Zahl in dieser Gruppe sein, dh die Gruppe der "Verlierer".
Die Größe dieser "Verlierer" -Gruppe ist log (N), und wiederum können wir die binären rekursiven Aufrufe widerrufen, um den größten unter den Verlierern zu finden. Tatsächlich können wir die Verlierergruppe einfach linear scannen, um auch die Antwort zu erhalten. Das Zeitbudget ist das gleiche.
Unten ist ein Beispiel für einen Python-Code:
def largest(L):
global paris
if len(L) == 1:
return L[0]
else:
left = largest(L[:len(L)//2])
right = largest(L[len(L)//2:])
pairs.append((left, right))
return max(left, right)
def second_largest(L):
global pairs
biggest = largest(L)
second_L = [min(item) for item in pairs if biggest in item]
return biggest, largest(second_L)
if __== "__main__":
pairs = []
# test array
L = [2,-2,10,5,4,3,1,2,90,-98,53,45,23,56,432]
if len(L) == 0:
first, second = None, None
Elif len(L) == 1:
first, second = L[0], None
else:
first, second = second_largest(L)
print('The largest number is: ' + str(first))
print('The 2nd largest number is: ' + str(second))
def SecondLargest(x):
largest = max(x[0],x[1])
largest2 = min(x[0],x[1])
for item in x:
if item > largest:
largest2 = largest
largest = item
Elif largest2 < item and item < largest:
largest2 = item
return largest2
SecondLargest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
Sie finden die zweitgrößte auf folgende Weise:
Option 1:
numbers = set(numbers)
numbers.remove(max(numbers))
max(numbers)
Option 2:
sorted(set(numbers))[-2]
def secondlarget(passinput):
passinputMax = max(passinput) #find the maximum element from the array
newpassinput = [i for i in passinput if i != passinputMax] #Find the second largest element in the array
#print (newpassinput)
if len(newpassinput) > 0:
return max(newpassinput) #return the second largest
return 0
if __name__ == '__main__':
n = int(input().strip()) # lets say 5
passinput = list(map(int, input().rstrip().split())) # 1 2 2 3 3
result = secondlarget(passinput) #2
print (result) #2
Ein einfacher Weg:
n=int(input())
arr = set(map(int, input().split()))
arr.remove(max(arr))
print (max(arr))
Um die akzeptierte Antwort allgemeiner zu machen, ist das folgende die Erweiterung, um den k-größten Wert zu erhalten:
def kth_largest(numbers, k):
largest_ladder = [float('-inf')] * k
count = 0
for x in numbers:
count += 1
ladder_pos = 1
for v in largest_ladder:
if x > v:
ladder_pos += 1
else:
break
if ladder_pos > 1:
largest_ladder = largest_ladder[1:ladder_pos] + [x] + largest_ladder[ladder_pos:]
return largest_ladder[0] if count >= k else None
Objective : Um die zweitgrößte Zahl aus der Eingabe zu finden.
Eingabe : 5 2 3 6 6 5
Ausgabe : 5
*n = int(raw_input())
arr = map(int, raw_input().split())
print sorted(list(set(arr)))[-2]*
Sie können dies auch versuchen:
>>> list=[20, 20, 19, 4, 3, 2, 1,100,200,100]
>>> sorted(set(list), key=int, reverse=True)[1]
100
Die meisten der vorherigen Antworten sind korrekt, aber hier ist ein anderer Weg!
Unsere Strategie besteht darin, eine Schleife mit zwei Variablen first_highest und second_highest zu erstellen. Wir durchlaufen die Zahlen und wenn unser current_value größer als der first_highest ist, dann setzen wir second_highest auf first_highest und dann second_highest als aktuelle Zahl. Wenn unsere aktuelle Nummer größer als second_highest ist, setzen wir second_highest auf die aktuelle Nummer 
#!/usr/bin/env python3
import sys
def find_second_highest(numbers):
min_integer = -sys.maxsize -1
first_highest= second_highest = min_integer
for current_number in numbers:
if current_number > first_highest:
second_highest = first_highest
first_highest = current_number
Elif current_number > second_highest:
second_highest = current_number
return second_highest
print(find_second_highest([80,90,100]))
n=input("Enter a list:")
n.sort()
l=len(n)
n.remove(n[l-1])
l=len(n)
print n[l-1]