Wat is de helft van een array en hoe bepaal je die…

De helft van een array (of de "mediaan" van de array, als deze gesorteerd is) is het element dat, als de array gesorteerd is, deze in twee delen deelt: elementen die kleiner of gelijk aan de mediaan zijn en elementen die groter of gelijk aan de mediaan zijn. Als het aantal elementen even is, wordt de mediaan vaak berekend als het rekenkundige gemiddelde van de twee centrale elementen. In de context van "de helft van de array" in sollicitatievragen kan ook worden verwezen naar het zoeken naar een meerderheids element dat meer dan N/2 keer voorkomt, waarbij N het aantal elementen in de array is.

De definitie van de helft van de array hangt af van de context:

Mediaan (voor een gesorteerde array of bij het zoeken naar het k-1e kleinste element):
- Sorteer de array.
- Als de grootte N oneven is, is de mediaan het element op index N/2.
- Als de grootte N even is, is de mediaan het rekenkundige gemiddelde van de elementen op indices N/2 - 1 en N/2.
Meerderheids- element (dat meer dan N/2 keer voorkomt):
- Gebruik het Boyer-Moore meerderheidsstem algoritme.
- Maak een variabele candidate en count.
- Loop door de array. Als het huidige element gelijk is aan candidate, verhoog count. Anders, en count > 0, verlaag count. Als count = 0, wordt het huidige element de nieuwe candidate, en wordt count op 1 gezet.
- Na de eerste pass is candidate een potentiële meerderheids- element. Om zeker te zijn, voer je een tweede pass uit om te bevestigen dat het daadwerkelijk meer dan N/2 keer voorkomt.

Voorbeeld van het bepalen van de mediaan (in Swift):

// Sorteren om de mediaan te vinden
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
    }
}

Voorbeeld van het bepalen van het meerderheids- element (in Swift):

// Boyer-Moore meerderheidsstem algoritme
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
        }
    }

    // Controleer of de kandidaat daadwerkelijk een meerderheids- element is
    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 // Geen meerderheids- element
}

Het is belangrijk om met de interviewer te verduidelijken welk specifiek type "helft van de array" wordt bedoeld in de context van de taak.

Wat is de helft van een array en hoe bepaal je die?