Massivning yarmi nima va uni qanday aniqlash mumkin…

Massivning yarmarkasi (yoki massivning "mediana"si, agar u tartiblangan bo'lsa) — bu element, agar massiv tartiblangan bo'lsa, uni ikki qismga bo'lib turadigan: medianadan kichik yoki teng bo'lgan elementlar va medianadan katta yoki teng bo'lgan elementlar. Agar elementlar soni juft bo'lsa, median odatda ikki markaziy elementning arifmetik o'rtacha hisoblanadi. Suhbat vazifalarida "massivning yarmi" kontekstida, shuningdek, N/2 dan ko'p marta uchraydigan majburiy elementni topish nazarda tutilishi mumkin, bu yerda N — massivdagi elementlar soni.

Massivning yarmi ta'rifi kontekstga bog'liq:

Median (tartiblangan massiv uchun yoki k-chi eng kichik elementni topishda):
- Massivni tartiblaymiz.
- Agar N toq bo'lsa, median N/2 indeksidagi element bo'ladi.
- Agar N juft bo'lsa, median N/2 - 1 va N/2 indekslaridagi elementlarning arifmetik o'rtachasi bo'ladi.
Majburiy element (N/2 dan ko'p marta uchraydigan):
- Boyer ovoz berish algoritmi (Boyer–Moore majority vote algorithm) dan foydalanamiz.
- candidate va count o'zgaruvchilarini yaratamiz.
- Massiv elementlarini aylanamiz. Agar hozirgi element candidate ga teng bo'lsa, count ni oshiramiz. Aks holda, va count > 0 bo'lsa, count ni kamaytiramiz. Agar count = 0 bo'lsa, hozirgi element yangi candidate bo'ladi va count 1 ga o'rnatiladi.
- Birinchi yurishdan so'ng, candidate ehtimoliy majburiy element bo'ladi. Uni tasdiqlash uchun ikkinchi yurishni amalga oshiramiz va u haqiqatan ham N/2 dan ko'p marta uchrayaptimi, tekshiramiz.

Swiftda mediani aniqlash misoli:

// Medianni topish uchun tartiblash
func findMedian(in array: [Int]) -> Double? {
    guard !array.isEmpty else { return nil }

    let sortedArray = array.sorted()
    let n = sortedArray.count

    if n % 2 == 1 {
        return Double(sortedArray[n / 2])
    } else {
        return Double(sortedArray[n / 2 - 1] + sortedArray[n / 2]) / 2.0
    }
}

Majburiy elementni aniqlash misoli (Swiftda):

// Boyer ovoz berish algoritmi
func findMajorityElement(in array: [Int]) -> Int? {
    var candidate: Int? = nil
    var count = 0

    for element in array {
        if count == 0 {
            candidate = element
            count = 1
        } else if element == candidate {
            count += 1
        } else {
            count -= 1
        }
    }

    // Kandidatning haqiqatan ham majburiy element ekanligini tekshirish
    var realCount = 0
    if let candidate = candidate {
        for element in array {
            if element == candidate {
                realCount += 1
            }
        }
        if realCount > array.count / 2 {
            return candidate
        }
    }

    return nil // Majburiy element topilmadi
}

Suhbatdosh bilan "massivning yarmi" nima ekanligini aniqroq tushunish muhimdir.

Massivning yarmi nima va uni qanday aniqlash mumkin?