Kas ir masīva puse un kā to noteikt?

Masyva puse (vai „mediana“ masīva, ja tas ir sakārtots) ir elements, kas, ja masīvs ir sakārtots, sadala to divās daļās: mazākos vai vienādus ar mediānu elementus un lielākus vai vienādus ar mediānu elementus. Ja elementu skaits ir pāra, bieži tiek uzskatīts, ka mediāna ir aritmētiskā vidējā divu centrālo elementu. Kontekstā „masīva puse” intervijas uzdevumos var arī nozīmēt meklēšanu majoritāra elementa, kas sastopams vairāk nekā N/2 reizes, kur N ir masīva elementu skaits.

Masīva puses definīcija ir atkarīga no konteksta:

1. Mediāna (sakārtotā masīvā vai meklējot k-tā mazākā elementa):

   • Sakārto masīvu.
   • Ja N ir nepāra, mediāna ir elements indeksā N/2.
   • Ja N ir pāra, mediāna ir aritmētiskā vidējā divu centrālo elementu indeksos N/2 - 1 un N/2.

2. Majoritāra elements (kas sastopams vairāk nekā N/2 reizes):

   • Izmanto Boyer–Moore vairākuma balsošanas algoritmu.
   • Izveido mainīgos candidate un count.
   • Pārlūko masīva elementus. Ja pašreizējais elements ir vienāds ar candidate, palielina count. Ja nav un count > 0, samazina count. Ja count = 0, pašreizējais elements kļūst par jauno candidate, un count tiek iestatīts uz 1.
   • Pēc pirmās pārejas candidate ir potenciālais majoritārais elements. Lai būtu droši, jāveic otra pāreja, lai pārliecinātos, ka tas patiešām sastopams vairāk nekā N/2 reizes.

Piemērs, kā noteikt mediānu (Swift):

// Sakārto un atrodi 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
    }
}

Piemērs, kā noteikt majoritāro elementu (Swift):

// Boyer–Moore vairākuma balsošanas algoritms
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
        }
    }

    // Pārbaudi, vai candidate ir patiešām majoritārs
    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 // Nav majoritāra elementa
}

Svarīgi ir precizēt ar intervijas vadītāju, kāda tieši ir „masīva puse” kontekstā.