So finden Sie den Median eines sehr großen Arrays in PHP

In PHP müssen wir manchmal ein sehr großes Array verarbeiten, beispielsweise um den Median zu ermitteln. Bei sehr großen Arrays ist die Verwendung herkömmlicher Sortiermethoden jedoch sehr zeitaufwändig und speicherintensiv. Gibt es also eine effizientere Möglichkeit, den Median eines sehr großen Arrays zu ermitteln? In diesem Artikel wird eine effiziente Lösungsmethode vorgestellt, die auf dem Schnellauswahlalgorithmus basiert.

1. Einführung in den Schnellauswahlalgorithmus

Der Schnellauswahlalgorithmus ist ein verbesserter Algorithmus, der auf dem Schnellsortierungsalgorithmus basiert. Seine Hauptidee besteht darin, das k-kleinste Element in einem ungeordneten Array durch schnelle Division zu finden. Seine Zeitkomplexität beträgt O(n), was effizienter ist als die Zeitkomplexität des herkömmlichen Sortieralgorithmus O(n log n).

Die grundlegenden Schritte des Schnellauswahlalgorithmus sind wie folgt:

1. Wählen Sie ein Pivot-Element aus (normalerweise das erste Element im Array);
2. Teilen Sie die Elemente im Array in zwei Teile, die kleiner als der Pivot und größer sind als der Pivot;
3. Wenn die Anzahl der Elemente, die kleiner als der Pivot sind, kleiner als k ist, wird weiterhin nach dem k-ten Element unter den Elementen gesucht, die größer als der Pivot sind.
4. Wenn die Anzahl der Elemente, die kleiner als der Pivot sind, größer oder gleich ist k, suchen Sie weiterhin nach dem k-ten Element unter den Elementen, die kleiner als das Pivot-Element sind;
5. Wiederholen Sie die obigen Schritte, bis das k-te Element gefunden wird.
6. Ermitteln des Medianwerts eines sehr großen Arrays

Wir betrachten nun, wie wir den Schnellauswahlalgorithmus verwenden können, um den Medianwert eines sehr großen Arrays zu ermitteln. Angenommen, wir haben ein sehr großes Array $nums$ und müssen seinen Median ermitteln. Wir führen zunächst eine schnelle Division von $nums$ durch und teilen die Elemente in zwei Teile auf, die kleiner als Pivot und größer als Pivot sind. Liegt der Pivot genau in der Mitte des Arrays, handelt es sich um den Median. Andernfalls können wir anhand der Position des Drehpunkts beurteilen, dass die Suche auf der Seite fortgesetzt werden sollte, auf der sich der Drehpunkt befindet.

Das Folgende sind die detaillierten Algorithmusschritte:

1. Zuerst müssen wir die Position der mittleren Mitte bestimmen. Wenn die Anzahl der Elemente $n$ im Array eine ungerade Zahl ist, ist der Median $nums[(n-1)/2]$; wenn die Anzahl der Elemente $n$ eine gerade Zahl ist, ist der Median $( Zahlen[n /2-1]+Zahlen[n/2])/2$.
2. Teilen Sie schnell das Array $nums$ und notieren Sie die Pivot-Position $pos$.
3. Bestimmen Sie anhand der Positionsbeziehung zwischen Pos und Mitte, ob der Median auf der linken oder rechten Seite des Pivots liegt. Wenn $pos< mid$, dann liegt der Median zwischen den Positionen $[pos+1,n-1]$; wenn $pos>=mid$, dann liegt der Median zwischen den Positionen $[0,pos-1]$.
4. Wiederholen Sie die Schritte 2 und 3, bis Sie den Median gefunden haben.

Das Folgende ist die entsprechende PHP-Code-Implementierung:

function quickSelect($nums, $k) {
    $n = count($nums);
    $left = 0;
    $right = $n - 1;
    $mid = ($n - 1) / 2;

    while (true) {
        $pos = partition($nums, $left, $right);
        if ($pos == $mid) {
            if ($n % 2 == 0) {
                // 偶数个元素
                return ($nums[$pos] + $nums[$pos + 1]) / 2;
            } else {
                // 奇数个元素
                return $nums[$pos];
            }
        } elseif ($pos < $mid) {
            $left = $pos + 1;
        } else {
            $right = $pos - 1;
        }
    }
}

function partition(&$nums, $left, $right) {
    $pivot = $nums[$left];
    $i = $left;
    $j = $right;

    while ($i < $j) {
        while ($i < $j && $nums[$j] >= $pivot) {
            $j--;
        }
        while ($i < $j && $nums[$i] <= $pivot) {
            $i++;
        }
        if ($i < $j) {
            $temp = $nums[$i];
            $nums[$i] = $nums[$j];
            $nums[$j] = $temp;
        }
    }

    // 将pivot元素放到正确的位置
    $nums[$left] = $nums[$i];
    $nums[$i] = $pivot;

    return $i;
}

// 测试示例
$nums = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
echo quickSelect($nums, 5); // 输出5（因为5在数组中的中间位置）

3. Zusammenfassung

Bei sehr großen Arrays bringt die Verwendung herkömmlicher Sortiermethoden eine sehr hohe zeitliche und räumliche Komplexität mit sich. Indem wir den schnellen Auswahlalgorithmus verwenden, um das k-kleinste Element zu finden, können wir die Operation innerhalb einer Zeitkomplexität von O(n) abschließen und so eine effiziente Lösung für den Median eines sehr großen Arrays erreichen. Es ist zu beachten, dass wir im tatsächlichen Gebrauch auch eine entsprechende Optimierung entsprechend unterschiedlichen Anforderungen durchführen müssen, z. B. Beschneiden usw.

Das obige ist der detaillierte Inhalt vonSo finden Sie den Median eines sehr großen Arrays in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!