Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumunion-find

Accounts Merge

Problem (yeniden ifade)

Her hesap [isim, e-posta…]. Herhangi bir e-postayı paylaşan hesapları birleştir. Çıktı [isim, sıralı benzersiz e-postalar…]. Yalnızca aynı isim birleştirmez.

Sezgi

Her hesap indeksini UF düğümü say. e-posta → ilk hesap id haritası; e-posta daha önce görülmüşse union.

Yaklaşımlar

Ortak e-postalı hesapları birleştir

Doğrulanmadı

Zaman O(N α(N) + E log E)Alan O(N + E)

Fikir. Birleştirmelerden sonra e-postaları köke göre grupla; her grubu sırala; kök hesabın ismini öne ekle.

Adım adım. johnsmith@mail.com paylaşan iki John hesabı tek sıralı e-posta listesine çöker.

Trade-off’lar. E-posta grafında BFS eşdeğer; UF daha kompakt.

Çözüm

export function accountsMerge(accounts: string[][]): string[][] {
  const n = accounts.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  const union = (a: number, b: number) => {
    const ra = find(a), rb = find(b);
    if (ra !== rb) parent[rb] = ra;
  };
  const emailToId = new Map<string, number>();
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < accounts[i]!.length; j++) {
      const email = accounts[i]![j]!;
      if (emailToId.has(email)) union(emailToId.get(email)!, i);
      else emailToId.set(email, i);
    }
  }
  const groups = new Map<number, Set<string>>();
  for (let i = 0; i < n; i++) {
    const r = find(i);
    if (!groups.has(r)) groups.set(r, new Set());
    for (let j = 1; j < accounts[i]!.length; j++) groups.get(r)!.add(accounts[i]![j]!);
  }
  const res: string[][] = [];
  for (const [r, emails] of groups) {
    res.push([accounts[r]![0]!, ...[...emails].sort()]);
  }
  return res;
}

export function accountsMerge(accounts: string[][]): string[][] {
  const n = accounts.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  const union = (a: number, b: number) => {
    const ra = find(a), rb = find(b);
    if (ra !== rb) parent[rb] = ra;
  };
  const emailToId = new Map<string, number>();
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < accounts[i]!.length; j++) {
      const email = accounts[i]![j]!;
      if (emailToId.has(email)) union(emailToId.get(email)!, i);
      else emailToId.set(email, i);
    }
  }
  const groups = new Map<number, Set<string>>();
  for (let i = 0; i < n; i++) {
    const r = find(i);
    if (!groups.has(r)) groups.set(r, new Set());
    for (let j = 1; j < accounts[i]!.length; j++) groups.get(r)!.add(accounts[i]![j]!);
  }
  const res: string[][] = [];
  for (const [r, emails] of groups) {
    res.push([accounts[r]![0]!, ...[...emails].sort()]);
  }
  return res;
}

Şablon bağlantısı

Eşdeğerlik sınıfları üzerinde Union-Find (paylaşılan anahtarlar).

Yansıma

Aynı e-postayı paylaşan hesaplar birleşir. İsim ilk görülen hesapta kalır. E-postalar sıralı yazılır.
Aynı isim, ortak e-posta yok: iki kişi. İsim anahtar değil.
Tek hesap e-postaları sıralı döner. Boş e-posta listesi bir grup üretmez.