Oder musst du den schnellsten Algorithmus findet?
ja sowas
Stammtisch & Kaffeekranzerl
-
-
ja sowas
Zeitkomplexität ist O(1) (immer die gleiche Rechenzeit, es wird ja über eine mathematische formel berechnet und nicht iterativ oder so)
Grobes Beispiel in Python:
def find_missing_number(nums):
# Sum of 1 to 100
total_sum = (100 * 101) // 2
# Sum of the given numbers
given_sum = sum(nums)
# Missing number
missing_num = total_sum - given_sum
return missing_num
# Example usage
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
missing_number = find_missing_number(nums)
print(missing_number) # 48
-
aso, du brauchst ne verallgemeinerung von dem algorithmus, mal gucken
-
Alles anzeigen
Zeitkomplexität ist O(1) (immer die gleiche Rechenzeit, es wird ja über eine mathematische formel berechnet und nicht iterativ oder so)
Grobes Beispiel in Python:
def find_missing_number(nums):
# Sum of 1 to 100
total_sum = (100 * 101) // 2
# Sum of the given numbers
given_sum = sum(nums)
# Missing number
missing_num = total_sum - given_sum
return missing_num
# Example usage
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
missing_number = find_missing_number(nums)
print(missing_number) # 48
Ist nat. nur O(1), wenn sum() O(1) ist
-
def find_missing_numbers(nums):
num_set = set(nums)
min_num = min(nums)
max_num = max(nums)
missing_numbers = []
steps = 0
for i in range(min_num, max_num+1):
steps += 1
if i not in num_set:
missing_numbers.append(i)
return missing_numbers, steps
Dann vielleicht sowas. Erstelle eine Menge von Zahlen von min_num (niedrigste Zahl) bis max_num (höchste Zahl). Die fehlenden Zahlen sind die Zahlen, die nicht in der Menge sind (leere Menge). Dann iterative Schleife, die die Menge nach den fehlenden Zahlen durchsucht. Zusätzlich die Iterationen zählen und am Ende fehlende Zahlen und Iterationen (Schritte) ausgeben. Die Zeitkomplexität dann halt O(N). Anzahl der Schritte wächst proportional mit der Größe der Menge.
(keine Garantie, dass das korrekt ist)
-
Eigentlich nicht, Summen werden bitweise berechnet, so wie wenn du zwei Zahlen auf dem Papier addierst mit "eins im Sinn".
https://de.wikipedia.org/wiki/Addierwerk
//nvm, ihr redet von einer Summenformel, da hast du vermutlich Recht.
-
Sicher. Und zur Berechnung der Summe über x Zahlen sind dann eben x solcher Rechenschritte notwendig. [Korrigiere: x-1 Schritte
]Es ging ja um die Rechendauer, richtig?
meinte schleife, sry
-
weil in Berlin wieder Wahlen sind, hier die Gretchenfrage: Wen wählen?
-
Das geringste Übel?
-
Also APPD!
-
-
Alles anzeigen
def find_missing_numbers(nums):
num_set = set(nums)
min_num = min(nums)
max_num = max(nums)
missing_numbers = []
steps = 0
for i in range(min_num, max_num+1):
steps += 1
if i not in num_set:
missing_numbers.append(i)
return missing_numbers, steps
Dann vielleicht sowas. Erstelle eine Menge von Zahlen von min_num (niedrigste Zahl) bis max_num (höchste Zahl). Die fehlenden Zahlen sind die Zahlen, die nicht in der Menge sind (leere Menge). Dann iterative Schleife, die die Menge nach den fehlenden Zahlen durchsucht. Zusätzlich die Iterationen zählen und am Ende fehlende Zahlen und Iterationen (Schritte) ausgeben. Die Zeitkomplexität dann halt O(N). Anzahl der Schritte wächst proportional mit der Größe der Menge.
(keine Garantie, dass das korrekt ist)
Wenn O(n), dann würde ich versuchen mit einem Array mit Zahlen von 1 bis 100 einfach das andere Array (wenn es sortiert ist) abgleichen. An i-ter stelle müssen beide Werte übereinstimmen, wenn nicht, hat man ein fehler gefunden. Damit müsste man dann halt auch alle möglichen fehlenden Zahlen finden können.
Im unsortierten Fall müsste man jede Zahl einzeln suchen, womit man dann bei n² angekommen wäre, denk ich.
-
Wenn O(n), dann würde ich versuchen mit einem Array mit Zahlen von 1 bis 100 einfach das andere Array (wenn es sortiert ist) abgleichen. An i-ter stelle müssen beide Werte übereinstimmen, wenn nicht, hat man ein fehler gefunden. Damit müsste man dann halt auch alle möglichen fehlenden Zahlen finden können.
Im unsortierten Fall müsste man jede Zahl einzeln suchen, womit man dann bei n² angekommen wäre, denk ich.
Wenn es sortiert ist, dann kannst das in O(logn) finden. Mit bissl Anpassung müsste es auch für mehr als einen Wert gehen. Von der Idee her schaust das Element in der Mitte an. Wenn es mit dem zu erwartenden übereinstimmt, dann gehst du weiter zur oberen Hälfte und schaust da in die Mitte, ansonsten ist das fehlende Element in der unteren Hälfte und du gehst da in die Mitte. Dem Algorithmus folgst du bis du das fehlende Element erreicht hast. Ach man muss wohl auch noch, wenn das in der Mitte nicht das zu erwartende ist prüfen ob es nicht schon direkt selbst das fehlende ist, dazu müsste ein Blick auf eins davor und eins danach ausreichen.
Im unsortierten Fall solltest du niemals schlechter als O(nlogn) sein, was der Worst-case für merge sort ist.
-
Wenn es sortiert ist, dann kannst das in O(logn) finden. Mit bissl Anpassung müsste es auch für mehr als einen Wert gehen. Von der Idee her schaust das Element in der Mitte an. Wenn es mit dem zu erwartenden übereinstimmt, dann gehst du weiter zur oberen Hälfte und schaust da in die Mitte, ansonsten ist das fehlende Element in der unteren Hälfte und du gehst da in die Mitte. Dem Algorithmus folgst du bis du das fehlende Element erreicht hast. Ach man muss wohl auch noch, wenn das in der Mitte nicht das zu erwartende ist prüfen ob es nicht schon direkt selbst das fehlende ist, dazu müsste ein Blick auf eins davor und eins danach ausreichen.
Im unsortierten Fall solltest du niemals schlechter als O(nlogn) sein, was der Worst-case für merge sort ist.
kannst du das auch abhängig von k machen bei k fehlenden Zahlen?
Wobei wenn zB jede ungerade Zahl fehlt, man ja dann O(k * log n) hat? Also, er sucht ja immer die Stelle, wo es auf der erwarteten Position ist. In dem Fall wäre es an 1. Stelle, dann fügt er da eine 2 ein, dann an 3. Stelle, fügt eine 4 ein usw.
-
kannst du das auch abhängig von k machen bei k fehlenden Zahlen?
Wobei wenn zB jede ungerade Zahl fehlt, man ja dann O(k * log n) hat? Also, er sucht ja immer die Stelle, wo es auf der erwarteten Position ist. In dem Fall wäre es an 1. Stelle, dann fügt er da eine 2 ein, dann an 3. Stelle, fügt eine 4 ein usw.
Ja du kannst das auch von k abhängig machen, dann musst halt bissl mehr buchhalten. Also jeweils prüfen wie hoch die Abweichung vom erwarteten Wert ist und wenn weniger als k, dann musst du in beide Richtungen weiter suchen.
Und wie du sagst, denke ich gerade auch, dass man dann im worst-case O(k logn) hat.
-
Ich war länger nicht hier... kann man im Forum jetzt auch mitlesen, ohne angemeldet zu sein?
-
-
Der Akt das "Moskauer Eis" in "Kiewer Eis" umzubenennen stellt einen symbolischen Akt der ... dar
Its all signals, but there is no substance.
Auch "smart" war der Schachzug von Rewe, damit zu werben, aus bekannten Gründen als DFB-Sponsor bei der WM auf Werbung zu verzichten. Die Sammelbildchen gabs trotzdem bei jedem Einkauf für die Zwerge und dürften dieses Mal nicht besonders beliebt gewesen sein.
Diese Art von Marketing braucht natürlich auch die passende Zielgruppe, die sich davon angesprochen fühlt. Wer kauft eigentlich bei diesen recht teuren Läden ein und dann ausgerechnet so ein Billig-Eis?
-
Ich weiß nicht wie sich das in den letzten Jahren entwickelt hat, aber mein Stand war das diese Läden tatsächlich alle ungefähr gleichteuer sind, wenn man eben zu den Billigmarken greift, nur dass in den "teuren" Läden halt das Angebot größer ist als bei Aldi/Lidl/Penny, und man daher natürlich auch teurer einkaufen kann.
-
Wer wirklich sparen muss, kauft offensichtlich immer noch oder wieder dort, wo die Versuchung geringer und die Moral zweitrangig ist. CO₂-Preise statt Euro für Bio-Artikel waren der neueste Coup und ein Hinweis darauf, wen man ansprechen möchte.
Jetzt mitmachen!
Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!