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

Hardquick-select

Find the Kth Largest Integer in the Array

Problem (yeniden ifade)

Tamsayılar string olarak (baştaki sıfır yok, "0" hariç; en fazla 100 basamak). k. en büyüğü string olarak döndür.

Sezgi

LC 215 ile aynı partition, sayısal string sırası: daha uzun daha büyük; eşit uzunluk → sözlük sırası. 64-bit int’e parse edilemez. Hedef indeks yine n-k.

Yaklaşımlar

Sayı dizgelerinde quick select

Doğrulanmadı

Zaman O(n · L) averageAlan O(1)

Fikir. cmp(a, b): uzunluk, sonra string. Rastgele partition, pivot n-k’ye oturana dek. O stringi döndür (dönüştürme).

Yürüyüş. ["3","6","7","10"], k=4 → en küçük → "3". ["2","21","12","1"], k=3 → "2".

Trade-off. Ortalama O(n) karşılaştırma, her biri O(L). n küçükse sıralama O(n log n · L) ve daha basit. Pivotu rastgele seç. Girdiyi yerinde değiştirir.

Çözüm

export function kthLargestNumber(nums: string[], k: number): string {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function cmp(a: string, b: string): number {
  if (a.length !== b.length) return a.length - b.length;
  return a < b ? -1 : a > b ? 1 : 0;
}

function partition(nums: string[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (cmp(nums[j]!, pivot) < 0) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

export function kthLargestNumber(nums: string[], k: number): string {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function cmp(a: string, b: string): number {
  if (a.length !== b.length) return a.length - b.length;
  return a < b ? -1 : a > b ? 1 : 0;
}

function partition(nums: string[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (cmp(nums[j]!, pivot) < 0) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

Şablon bağlantısı

Özel sıralı Quick Select. LC 215 aynı döngünün tamsayı hali.

Yansıma

Sayı dizgesi. Önce uzunluk, aynı uzunlukta sözlük sırası. Kısa olan küçük. Başa sıfır yok.
Sayıya çevirmek taşar. k’ıncı büyük quickselect bu sırayla bölünür.
k = 1 en büyük. Eşit dizgiler aynı sırada. 9 ile 10: uzun olan büyük.