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

Count of Smaller Numbers After Self

Problem (yeniden ifade)

Her i için j > i ve nums[j] < nums[i] kaç tane say. Bu sayıların dizisini döndür.

Sezgi

Sağdan sola yürü ki “kendinden sonra” “zaten eklenmiş” olsun. Sıklık Fenwick’i, sıkıştırılmış rütbe ile indekslenmiş, “eklenen değerlerden < x kaç tane”yi önek toplamı olarak cevaplar. Sonra x’i ekle.

Yaklaşımlar

Sıkıştırılmış rütbede Fenwick

Doğrulanmadı

Zaman O(n log n)Alan O(n)

Fikir. Tekil değerleri sıralayıp rütbe ver. Sağdan: ans[i] = prefixSum(rank[x]-1), sonra update(rank[x], +1).

Yürüyüş. [5,2,6,1]. 1 ekle (0 küçük). 6 ekle (1). 2 ekle (1). 5 ekle (2). Sonuç [2,1,1,0].

Trade-off. Değerler küçük 0..n aralığında olmadığı için koordinat sıkıştırma şart. Merge-sort inversiyon sayımı eşdeğer böl-yönet okuması.

Çözüm

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function countSmaller(nums: number[]): number[] {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  const res = new Array<number>(nums.length).fill(0);
  for (let i = nums.length - 1; i >= 0; i--) {
    const r = rank.get(nums[i]!)!;
    res[i] = bit.prefixSum(r - 1);
    bit.update(r, 1);
  }
  return res;
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function countSmaller(nums: number[]): number[] {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  const res = new Array<number>(nums.length).fill(0);
  for (let i = nums.length - 1; i >= 0; i--) {
    const r = rank.get(nums[i]!)!;
    res[i] = bit.prefixSum(r - 1);
    bit.update(r, 1);
  }
  return res;
}

Şablon bağlantısı

BIT dinamik frekans tablosu. LC 493 ve LC 1649 aynı “sorgula sonra ekle” yürüyüşü, farklı yüklemle.

Yansıma

Sağdan sola. BIT o ana kadar görülen daha küçüklerin sayısı. Değerler sıkıştırılmış sıra.
Önce sor, sonra ekle. Eşit değer daha küçük sayılmaz. Soldan sağa taramak soldakileri sayar.
Tek eleman 0. Artan dizide herkes 0. Azalan dizide soldan sağa sayılar n-1’den 0’a iner.