Mi az egy tömb fele és hogyan határozzuk meg?

Egy tömb (vagy ha rendezett, akkor a tömb "mediánja") fele az az elem, amely, ha a tömb rendezett, két részre osztja azt: azokat az elemeket, amelyek kisebbek vagy egyenlőek a mediánnal, és azokat, amelyek nagyobbak vagy egyenlőek a mediánnal. Ha az elemek száma páros, a medián gyakran a két központi elem aritmetikai átlaga. Az "array felének" fogalma a kontextustól függ:

1. Medián (rendezett tömb vagy a k-ik legkisebb elem keresése esetén):

   • Rendezze a tömböt.
   • Ha a N méret páratlan, a medián a N/2 indexű elem.
   • Ha a N méret páros, a medián a N/2 - 1 és N/2 indexű elemek aritmetikai átlaga.

2. Többségi elem (amely több mint N/2 alkalommal fordul elő):

   • Használja a Boyer szavazási algoritmust (Boyer–Moore többségi szavazási algoritmus).
   • Hozzon létre egy candidate és count változót.
   • Iteráljon végig a tömb elemein. Ha az aktuális elem megegyezik a candidate-tel, növelje a count-ot. Ha nem, és a count > 0, csökkentse a count-ot. Ha a count = 0, az aktuális elem lesz az új candidate, és a count értéke 1 lesz.
   • Az első pass után a candidate egy potenciális többségi elem. Hogy biztosak legyünk benne, végezzünk egy második pass-t, hogy megerősítsük, valóban több mint N/2 alkalommal fordul elő.

Swift példák a medián meghatározására:

// Rendezés a medián megtalálásához
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
    }
}

A többségi elem meghatározására:

// Boyer többségi szavazási algoritmus
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
        }
    }

    // Ellenőrizze, hogy a jelölt valóban többségi elem-e
    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 // Nincs többségi elem
}

Fontos tisztázni a kérdezővel, hogy pontosan milyen típusú "array felének" értendő a kérdéskör.