Mis on massiivi pool ja kuidas seda määrata?

Massiivi pool (või „mediaan” massiiv, kui see on sorteeritud) on element, mis, kui massiiv on sorteeritud, jagab selle kaheks osaks: väiksemad või võrdsed mediaaniga elemendid ja suuremad või võrdsed mediaaniga elemendid. Kui elementide arv on paaritu, loetakse sageli mediaaniks kahe keskse elemendi aritmeetilist keskmist. Kontekstis „massivi pool” intervjuu ülesannetes võib mõista ka mahusõbraliku elemendi otsimist, mis esineb rohkem kui N/2 korda, kus N on massiivi elementide arv.

Massiivi poole määratlus sõltub kontekstist:

1. Mediaan (sorteeritud massiiv või k-nda väiksema elemendi otsimisel):

   • Sorteerime massiivi.
   • Kui N on paaritu, on mediaan element indeksil N/2.
   • Kui N on paaris, on mediaan kahe keskse elemendi aritmeetiline keskmine indeksitel N/2 - 1 ja N/2.

2. Mahtõrnaline element (esineb rohkem kui N/2 korda):

   • Kasutame Boyer–Moore enamusvalimise algoritmi.
   • Loome muutujad candidate ja count.
   • Läbime massiivi elemendid. Kui praegune element võrdub candidate-ga, suurendame count-i. Kui ei ja count > 0, vähendame count-i. Kui count = 0, praegune element saab uueks candidate-ks ja count seatakse 1-ks.
   • Pärast esimest läbimist on candidate potentsiaalne mahtõrnaline element. Kindluse huvides tuleb teha teine läbimine, et veenduda, et ta tõesti esineb rohkem kui N/2 korda.

Näide mediaani määramisest (Swift):

// Sorteeri ja leia mediaan
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
    }
}

Näide mahtõrnalise elemendi määramisest (Swift):

// Boyer–Moore enamusvalimise algoritm
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
        }
    }

    // Kontrolli, kas kandidaat on tõesti mahtõrnaline
    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 // Mahtõrnalist elementi pole
}