Was ist die Hälfte eines Arrays und wie bestimmt man…

Die Hälfte eines Arrays (oder die "Median" des Arrays, wenn es sortiert ist) ist das Element, das, wenn das Array sortiert ist, es in zwei Teile teilt: Elemente, die kleiner oder gleich der Median sind, und Elemente, die größer oder gleich der Median sind. Wenn die Anzahl der Elemente gerade ist, wird die Median oft als arithmetisches Mittel der beiden zentralen Elemente berechnet. Im Kontext von "der Hälfte des Arrays" in Vorstellungsgesprächen kann auch die Suche nach einem Mehrheitselement gemeint sein, das mehr als N/2 Mal vorkommt, wobei N die Anzahl der Elemente im Array ist.

Die Definition der Hälfte des Arrays hängt vom Kontext ab:

Median (für ein sortiertes Array oder bei der Suche nach dem k-kleinsten Element):
- Wir sortieren das Array.
- Wenn die Größe N ungerade ist, ist die Median das Element bei Index N/2.
- Wenn die Größe N gerade ist, ist die Median das arithmetische Mittel der Elemente bei den Indizes N/2 - 1 und N/2.
Mehrheits-Element (das mehr als N/2 Mal vorkommt):
- Wir verwenden den Boyer-Moore Mehrheitswahl-Algorithmus.
- Wir erstellen eine Variable candidate und count.
- Wir durchlaufen die Array-Elemente. Wenn das aktuelle Element gleich candidate ist, erhöhen wir count. Wenn nicht, und count > 0, verringern wir count. Wenn count = 0, wird das aktuelle Element zum neuen candidate, und count wird auf 1 gesetzt.
- Nach dem ersten Durchlauf ist candidate ein potenzielles Mehrheits-Element. Um sicherzugehen, führen wir einen zweiten Durchlauf durch, um zu bestätigen, dass es tatsächlich mehr als N/2 Mal vorkommt.

Beispiel zur Bestimmung der Median (in Swift):

// Sortieren, um die Median zu finden
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
    }
}

Beispiel zur Bestimmung des Mehrheits-Elements (in Swift):

// Boyer-Moore Mehrheitswahl-Algorithmus
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
        }
    }

    // Überprüfung, ob der Kandidat tatsächlich Mehrheits-Element ist
    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 // Kein Mehrheits-Element
}

Es ist wichtig, mit dem Interviewer zu klären, welchen genauen Typ von "Hälfte des Arrays" in der Aufgabenstellung gemeint ist.

Was ist die Hälfte eines Arrays und wie bestimmt man sie?