Массивдин жарымы эмне жана аны кантип аныктоо керек…

Массивдин жарымы (жеки "медиана" массиви, эгер ал сорттолгон болсо) — бул элемент, эгер массив сорттолгон болсо, аны эки бөлүккө бөлөт: медианага караган кичүү же барабар элементтер жана чоңураак же барабар элементтер. Эгер элементтердин саны так болсо, медиана көбүнчө эки борбордук элементтин ортоңку арифметикалык орточо деп эсептелет. "Массивдин жарымы" түшүнүгү интервью тапшырмаларында ошондой эле > N/2 жолу кездешкен мажоритардык элементти издөө болушу мүмкүн, анда N — массивдеги элементтердин саны.

Массивдин жарымын аныктоо контекстке көз каранды:

Медиана (сорттолгон массив үчүн же k-чи эң кичүү элементти издөөдө):
- Массивди сорттоп чыгуу.
- Эгер N так эмес болсо, медиана N/2 индексиндеги элемент болот.
- Эгер N так болсо, медиана N/2 - 1 жана N/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 // Мажоритардык элемент жок
}

Интервью берүүчү менен "массивдин жарымы" деген эмне экенин тактоо маанилүү.

Массивдин жарымы эмне жана аны кантип аныктоо керек?