Mediumhashing

Longest Consecutive Sequence

Problem (yeniden ifade)

En uzun ardışık eleman dizisinin uzunluğunu döndür. O(n) zamanda çalışmalı.

Sezgi

Sayıları bir sete koy. Yalnızca öncülü olmayan sayılardan saymaya başla.

Yaklaşımlar

Hash set yalnızca başlangıçlar

Verified

Time O(n)Space O(n)

Fikir. x-1 eksik olan her x için x, x+1, … eksilene kadar say. Maks seriyi tut.

Adım adım. [100,4,200,1,3,2] → 1’den başla → 1..4 uzunluk 4.

Trade-off’lar. Sıralama daha basit O(n log n) ama O(n) kısıtını bozar.

Solution

export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let y = x, len = 1;
    while (set.has(y + 1)) { y++; len++; }
    best = Math.max(best, len);
  }
  return best;
}

export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let y = x, len = 1;
    while (set.has(y + 1)) { y++; len++; }
    best = Math.max(best, len);
  }
  return best;
}

Yansıma

90 saniyenin altında hangi ipucu bu kalıbı seçtirdi?
Hangi girdi yanlış bir değişmezi bozar?