Čo je polovica poľa a ako ju určiť?

Polovica poľa (alebo "medián" poľa, ak je zoradené) je prvok, ktorý, ak je pole zoradené, delí ho na dve časti: prvky menšie alebo rovné mediánu a prvky väčšie alebo rovné mediánu. Ak je počet prvkov párny, medián sa často považuje za aritmetický priemer dvoch stredných prvkov. V kontexte "poloviny poľa" v úlohách na pohovore môže byť tiež myslené hľadanie majoritného prvku, ktorý sa vyskytuje viac ako N/2 krát, kde N je počet prvkov v poli.

Definícia poloviny poľa závisí od kontextu:

1. Medián (pre zoradené pole alebo pri hľadaní k-tého najmenšieho prvku):

   • Zoradíme pole.
   • Ak je veľkosť N nepárna, medián je prvok na indexe N/2.
   • Ak je veľkosť N párna, medián je aritmetický priemer prvkov na indexoch N/2 - 1 a N/2.

2. Majoritný prvok (prvok, ktorý sa vyskytuje > N/2 krát):

   • Používame algoritmus hlasovania Boyera (Boyer–Moore majority vote algorithm).
   • Vytvoríme premenné candidate a count.
   • Prechádzame prvky poľa. Ak je aktuálny prvok rovný candidate, zvýšime count. Ak nie, a count > 0, znížime count. Ak je count = 0, aktuálny prvok sa stáva novým candidate a count sa nastaví na 1.
   • Po prvom prechode je candidate potenciálnym majoritným prvkom. Pre istotu je potrebné vykonať druhý prechod, aby sa overilo, že sa naozaj vyskytuje viac ako N/2 krát.

Príklad určenia mediánu (v Swift):

// Zoradenie pre nájdenie mediánu
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
    }
}

Príklad určenia majoritného prvku (v Swift):

// Algoritmus hlasovania Boyera
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
        }
    }

    // Kontrola, či je kandidát naozaj majoritným prvkom
    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 // Žiadny majoritný prvok
}

Je dôležité sa spýtať na zadávateľa, aký presne typ "poloviny poľa" má na mysli v kontexte úlohy.