Algorithmen und Datenstrukturen · Middle · Frage 72 von 75
Was macht diese Funktion, und welche Komplexität hat sie?
function f(nums) {
const seen = new Set(nums);
let best = 0;
for (const x of seen) {
if (seen.has(x - 1)) continue;
let len = 1;
while (seen.has(x + len)) len++;
best = Math.max(best, len);
}
return best;
}- 1Längste Folge lückenloser Zahlen, O(n)
- 2Die Zahl der Duplikate, O(n²)
- 3Die größte Zahl im Array, O(n log n)
Antwort zeigen
Richtige Antwort: Längste Folge lückenloser Zahlen, O(n)
Erklärung
Eine Folge wird nur ab ihrer kleinsten Zahl gezählt (wenn x - 1 fehlt), jede Zahl wird in der inneren Schleife also höchstens einmal geprüft. Sortieren ergäbe O(n log n).