Graph protsessing özining eng yuqori çöqqisi - maxflow/mincut masalasidan keyin tugadi (hozirça). Biz graph'ga Leetcode masalalarini yeçiş jarayonida yana qaytamiz. Keyingi maqolalarda osonroq mavzular - string va string sort haqida söz boradi.

Javascriptda har bir string belgi UTF-16 belgilarining qöllab quvvatlanişi sababli xotiradan 4 baytgaça joy oladi (ammo hamma UTF-16 belgilar ham qöllab-quvvatlanmaydi, çunki hamma UTF-16 belgilar ham 4 bayt emas). Misol uçun, Blob yordamida biz strinğning hajmini bila olamiz.

console.info(
  new Blob(['😂']).size,               // 4
  new Blob(['👍']).size,               // 4
  new Blob(['😂👍']).size,             // 8
  new Blob(['I\'m a strinğ]).size,   // 12, har bir belgi uçun 1 bayt
);

Amaliyotda UTF-16 belgilari köp ham işlatilmasligi bois, misollarda biz oddiy ASCII belgilar bilan çeklanamiz.

Radix

Radix (radiks) - biror alifbodagi (yoki tizimdagi) unikal belgilar soniga teng. Masalan, ikkilik sanoq tizimi uçun R = 2 (0 1); 16lik sanoq tizimida R = 16 (0123456789ABCDEF); ASCII uçun R = 128; va hokazo.

Biz masala yeçiş jarayonida radix sonini stringdagi unikal qiymatlarga köra aniqlab olişimiz ham mumkin, biz uçun radix soni dunyo standartlari böyiça bölişi şartmas.

Key indeksli sanoq

Key indeksli sanoq (bundan keyin Key indexed counting, KIC) bizga unikal bölmagan key'ga ega röyhatlarni tartiblaş uçun asqotişi bois, dastlab biz tartiblaş algoritmlari haqida eslab olamiz.

Samarador tartiblaş algoritmlari - Mergesort, Quicksort va Heapsort da time complexity O(N lg N) dan katta edi, ya'ni tartiblaş uçun N elementlarni N lg N marta taqqoslaş talab etilardi.

Amaliyotda kiçik integer key'li, köpinça key'lari unikal bölmagan röyhatlar uçraydi. Masalan, röyhatdagi sözlarni boş harfi böyiça tartiblaş yoki telefon raqamlarini joy kodi böyiça tartiblaş. Javascriptda odatiy Array.sort() funksiyasi bilan tartiblaşdan qutiliş mumkin, bu oson yöl, töğri. Ammo .sort() funksiyasi ham Quicksort/Mergesort algoritmi asosida işlaydi.

Bizga qöyiladigan savol - string key'li röyhatni tartiblaş uçun biz yaxşiroq natijaga erişişimiz mumkinmi?

Bizda quyidagi röyhat bor:

Uni section böyiça tartiblaş kerak. Bunda section'ga boğlangan ismlar joylaşuvi ham özgaradi. Key'lar unikalmas, va ular kiçik integer sonlardan taşkil topgan. Şu faktga köra, key'larni array indeksi deb olib, tezkor tartiblaşni amalga oşiriş mumkin.

Key'lar röyhatini olamiz:

const sections = [
  2, 3, 3, 4, 1, 3, 4,
  3, 1, 2, 2, 1, 2, 4,
  3, 4, 4, 2, 3, 4
]

Key'larning sections[] da neça marta qaytarilayotganini aniqlab olamiz.

const count = []
const count = Array(R + 1).fill(0) // R - radix, unikal belgilar soni

for (let i = 0; i < sections.length; i++) {
  count[sections[i]]++
}

Şunda bizda count[]

[ 0, 3, 5, 6, 6 ]

1 key 3 marta qaytarilayotgan ekan, 2 5 marta, 3 6 marta, 4 ham 6 marta. Endi qaytarilişlarni ketma-ketlikka almaştiramiz.

for (let i = 0; i < R; i++) {
  count[i + 1] += count[i]
}

count[] endi

[ 0, 3, 8, 14, 20 ]

bu röyhat sections'dagi key'larning umumiy röyhatda qaysi qatordan boşlanişini bildiradi. Faqat endi section 1 count[0] dan boşlab hisoblanadi. sections'ni tartiblab yangi aux[] array'ga yiğamiz.

for (let i = 0; i < sections.length; i++) {
  aux[count[sections[i] - 1]++] = sections[i]
}

aux[] qiymati:

[ 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4 ]

Yuqoridagi siklni kengaytirib, röyhatni tartiblaymiz.

for (let i = 0; i < sections.length; i++) {
  const newPosition = count[sections[i] - 1]++
  auxNames[newPosition] = names[i]
  aux[newPosition] = sections[i]
}

Bizdagi röyhat tartiblandi:

Töliq kod bilan tanişib çiqişingiz mumkin:

P.s. Key string bölsa, hisoblaşlardan oldin str.charCodeAt() funksiyasi bilan string belgini indeksga özgartiriş kerak böladi.