Kas yra masyvo pusė ir kaip ją nustatyti?

Pusė masyvo (arba „medianos“ masyvo, jei jis yra surūšiuotas) yra elementas, kuris, jei masyvas yra surūšiuotas, padalija jį į dvi dalis: mažesnius arba lygius medianai elementus ir didesnius arba lygius medianai elementus. Jei elementų skaičius yra lyginis, medianą dažnai laiko aritmetiniu vidurkiu dviejų centrinio elemento. Kontekste „masyvo pusė“ interviu užduotyse gali būti taip pat reiškiama ieškant majoritarinio elemento, kuris pasikartoja daugiau nei N/2 kartų, kur N yra masyvo elementų skaičius.

Masyvo pusės apibrėžimas priklauso nuo konteksto:

1. Mediana (surenkiuotame masyve arba ieškant k-tojo mažiausio elemento):

   • Surūšiuojame masyvą.
   • Jei N yra nelyginis, mediana yra elementas indeksu N/2.
   • Jei N yra lyginis, mediana yra dviejų centrinių elementų aritmetinis vidurkis indeksais N/2 - 1 ir N/2.

2. Majoritarinis elementas (pasikartojantis daugiau nei N/2 kartų):

   • Naudojame Boyer–Moore daugumos balsavimo algoritmą.
   • Sukuriame kintamuosius candidate ir count.
   • Peržvelgiame masyvo elementus. Jei dabartinis elementas yra lygus candidate, didiname count. Jei ne ir count > 0, mažiname count. Jei count = 0, dabartinis elementas tampa nauju candidate, o count nustatomas į 1.
   • Po pirmojo praeities candidate yra potencialus majoritarinis elementas. Norint įsitikinti, reikia atlikti antrą praeitį, kad įrodytume, jog jis tikrai pasikartoja daugiau nei N/2 kartų.

Pavyzdys, kaip nustatyti medianą (Swift):

// Surūšiuoti ir rasti medianą
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
    }
}

Pavyzdys, kaip nustatyti majoritarinį elementą (Swift):

// Boyer–Moore daugumos balsavimo algoritmas
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
        }
    }

    // Patikriname, ar candidate tikrai majoritarinis
    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 // Nėra majoritarinio elemento
}

Svarbu pasitikslinti su interviu vedėju, kokio tipo „masyvo pusė“ jis turi omenyje kontekste užduoties.