Takrorlanish bormi?

Ro'yxatda bir qiymat bir necha marta uchragan bo'lsa, buni aniqlash kerak. Bu juda oddiy savol ko'rinadi, lekin uni samarali yechish hashlashning asosiy "Ko'rildi" shablonini to'liq namoyon qiladi.

Masala: butun sonlar ro'yxati berilgan. Ro'yxatda biror son kamida ikki marta uchraydi-uchramaganini aniqlang.

[1, 2, 3, 1]   → TRUE   (1 ikki marta)
[1, 2, 3, 4]   → FALSE  (hech biri takrorlanmagan)
[1, 1, 1, 3]   → TRUE   (1 uch marta)

To'g'ridan-to'g'ri yondashuv

Eng tushunarli yondashuv: har element uchun qolgan barcha elementlarni tekshirish.

FUNCTION HAS_DUPLICATE_BRUTE(nums)
    FOR i = 0 DAN n-1 GACHA
        FOR j = i+1 DAN n-1 GACHA
            IF nums[i] = nums[j]
                RETURN TRUE
    RETURN FALSE

Bu to'g'ri ishlaydi, lekin n ta elementli ro'yxatda taxminan n*(n-1)/2 ta taqqoslash bajariladi. Vaqt murakkabligi O(n²). 100 elementda 5 000 ta taqqoslash, 10 000 elementda 50 million ta.

Muammo shundaki, har element uchun "bu qiymatni avval ko'rganmidim?" savoliga barcha oldingi elementlarni qaytadan ko'rib javob berilmoqda. Bu ishni bir marta saqlasak bo'ladi.

Saralash bilan yondashuv

Saralangach, takroriy elementlar qo'shni bo'ladi:

[3, 1, 4, 1, 5]  →  saralangach  →  [1, 1, 3, 4, 5]
                                        ↑ ↑
                                    qo'shni takroriy

FUNCTION HAS_DUPLICATE_SORT(nums)
    nums ni sarala

    FOR i = 0 DAN n-2 GACHA
        IF nums[i] = nums[i+1]
            RETURN TRUE

    RETURN FALSE

Vaqt: O(n log n) (saralash), xotira: O(1) yoki O(log n) (saralash algoritmi rekursiyasiga qarab). Bu yaxshi yondashuv, lekin asl ro'yxatni o'zgartiradi. Bundan tashqari, noldan yaxshiroq — O(n) — bo'lish mumkin.

Hash set bilan yondashuv

Asosiy g'oya: ro'yxatni bir marta o'qib, har element uchun "buni avval ko'rganmidim?" savolini doimiy vaqtda javoblash.

Ko'rilgan elementlarni hash setda saqlaymiz. Yangi element uchraganda, avval setda bormi tekshiramiz. Bor bo'lsa — takrorlangan; yo'q bo'lsa — setga qo'shib davom etamiz.

FUNCTION HAS_DUPLICATE(nums)
    seen = bo'sh hash set

    FOR har bir num nums ichida
        IF seen CONTAINS num
            RETURN TRUE
        seen ADD num

    RETURN FALSE

Ro'yxat bir marta o'qiladi. Har element uchun CONTAINS va ADD — ikkisi ham kutiladigan O(1). Jami vaqt O(n).

Bosqichma-bosqich dry run

[3, 1, 4, 1, 5, 9]:

num=3: seen = {}    → 3 yo'q → ADD(3)   seen: {3}
num=1: seen = {3}   → 1 yo'q → ADD(1)   seen: {3, 1}
num=4: seen = {3,1} → 4 yo'q → ADD(4)   seen: {3, 1, 4}
num=1: seen = {3,1,4} → 1 bor → RETURN TRUE

[1, 2, 3, 4, 5]:

num=1: 1 yo'q → ADD(1)
num=2: 2 yo'q → ADD(2)
num=3: 3 yo'q → ADD(3)
num=4: 4 yo'q → ADD(4)
num=5: 5 yo'q → ADD(5)

Tsikl tugadi → RETURN FALSE

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira	Eslatma
Ikki tsikl	`O(n²)`	`O(1)`	Asl ro'yxat o'zgarmaydi
Saralash	`O(n log n)`	`O(1)`–`O(log n)`	Asl tartib o'zgarishi mumkin
Hash set	`O(n)`	`O(n)`	Eng tez, qo'shimcha xotira ishlatadi

Hash set yondashuvi eng yaxshi vaqt murakkabligini beradi, lekin eng ko'p qo'shimcha xotira talab qiladi. Xotira qat'iy cheklangan bo'lsa va ro'yxatni o'zgartirishga ruxsat bo'lsa, saralash o'rtacha murosali yechim.

Hash set'da eng yomon holat O(n) emas, balki kutiladigan O(n). Barcha elementlar bir bucketga tushib, lookuplar O(n) bo'lsa, jami O(n²). Amalda bu deyarli sodir bo'lmaydi.

Edge case'lar

Bo'sh ro'yxat. For tsikli bajarmaydi, FALSE qaytariladi. Hech element yo'q — takrorlangan ham yo'q.

Bitta element. Setga qo'shiladi, tsikl tugaydi, FALSE. To'g'ri — bitta element takrorlanmagan.

Hammasi bir xil. [5, 5, 5, 5] — ikkinchi 5 uchraganda darhol TRUE.

Faqat ikkita element, teng. [7, 7] — birinchi 7 setga, ikkinchi uchraganda TRUE.

Faqat ikkita element, har xil. [7, 8] — ikkisi ham setga, FALSE.

Manfiy sonlar. Manfiy sonlar hash set uchun alohida holat emas; ular ham kalit sifatida ishlaydi.

Masalaning variantlari

Takroriy elementni qaytarish. RETURN TRUE o'rniga takroriy num qaytarilsa, "qaysi element takrorlandi" ham ma'lum bo'ladi.

Necha marta takrorlangani. Hash map ishlatilsa, num → count saqlanib, necha marta uchragani hisoblanadi.

K masofada takrorlangan. "Masofasi k dan oshmaydigan ikkita bir xil element bor" masalasida sliding window va hash set birga ishlatiladi: window'dan tashqariga chiqgan element setdan o'chiriladi.

Takroriy elementlarni o'chirish. Barcha noyob elementlarni qoldirish kerak bo'lsa, chastota mapida 1 dan katta elementlar o'chiriladi.

Xulosa

Takrorlanish masalasi "Ko'rildi" shablonining eng sodda ko'rinishi. Hash set har elementni bir marta ko'rib, avval uchragan-uchramaganini O(1) da tekshiradi. Bu O(n²) ikki tsikldan O(n) ga keskin yaxshilanish; narxi — O(n) qo'shimcha xotira.

Bu mantiq graflar BFS/DFS'dagi visited, dinamik dasturlashdagi memoization va turli "bir ro'yxatdagi ikki element" masalalarida qayta-qayta ishlatiladigan asosiy qurilish blokidir.