Нимояи нимояи массив ва чӣ гуна муайян кардан?

Нимояи масив (ёки "медиана" масив, агар он сортшуда бошад) — ин унсури аст, ки агар масив сортшуда бошад, онро ба ду қисм тақсим мекунад: унсурҳое, ки камтар ё баробар бо медиана ҳастанд ва унсурҳое, ки бештар ё баробар бо медиана ҳастанд. Агар шумораи унсурҳо чен бошад, медиана одатан ҳисоб мешавад бо миёнаи арифметикии ду унсури марказӣ. Дар контексти "нимояи масив" дар вазифаҳои мусоҳиба метавонад маънои ёфтан мажоритарӣ унсурро дошта бошад, ки бештар аз N/2 бор дар масив пайдо мешавад, ки N — шумораи унсурҳо дар масив.

Таъриф кардани нимояи масив вобаста ба контекст:

1. Медиана (барои масиви сортшуда ё дар ҷустуҷӯи унсури к-ум):

   • Масивро сорт мекунем.
   • Агар андозаи N непарран бошад, медиана унсури дар индекс N/2 аст.
   • Агар андозаи N парран бошад, медиана миёнаи арифметикии унсурҳои дар индексҳои N/2 - 1 ва N/2 аст.

2. Унсури мажоритарӣ (ки бештар аз N/2 бор дар масив аст):

   • Алгоритми овоздиҳии Бойер (Boyer–Moore majority vote algorithm) истифода мекунем.
   • Маъзур candidate ва count месозем.
   • Унсурҳоро мегузаронем. Агар унсури ҳозира баробари candidate бошад, count-ро зиёд мекунем. Агар не, ва count > 0, count-ро кам мекунем. Агар count = 0, унсури ҳозира ба candidate табдил меёбад ва count ба 1 баробар мешавад.
   • Пас аз гузариши аввал, candidate эҳтимолан унсури мажоритарӣ аст. Барои бехатарӣ, бояд гузариши дуввум анҷом дода шавад, то боварӣ ҳосил шавад, ки он воқеан бештар аз N/2 бор аст.

Масалан, муайян кардани медиана (дар Swift):

// Сортинг барои ёфтани медиана
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
    }
}

Масалан, муайян кардани унсури мажоритарӣ (дар Swift):

// Алгоритми овоздиҳии Бойер
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
        }
    }

    // Санҷед, ки оё candidate воқеан унсури мажоритарӣ аст
    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 // Ҳеҷ унсури мажоритарӣ нест
}

Муҳим аст, ки бо мутаҳассис дар бораи навъи "нимояи масив" дар контексти вазифа суҳбат кунед.