Bagaimana untuk mencari median daripada tatasusunan tidak tertib dalam php

Dalam PHP, tatasusunan ialah struktur data yang sangat berkuasa. Dengan tatasusunan PHP, kami boleh menyimpan dan memanipulasi sejumlah besar data dengan mudah. Tetapi apa yang kita lakukan apabila kita perlu mencari median daripada tatasusunan yang tidak tertib?

Median (juga dipanggil median) ialah nilai tengah dalam tatasusunan, yang membahagikan tatasusunan kepada dua bahagian Semua nilai di sebelah kiri adalah lebih kecil daripadanya dan semua nilai di sebelah kanan adalah lebih besar. Jika tatasusunan mempunyai bilangan elemen genap, median ialah purata dua elemen tengah.

Walaupun PHP menyediakan fungsi sort(), yang boleh digunakan untuk mengisih tatasusunan, apabila mengisih tatasusunan besar, kerumitan masa fungsi ini akan mencapai O(nlogn) dan pengisihan tatasusunan akan diubah suai. perintah, ini bukan yang kita mahu.

Jadi, bagaimanakah kita mencari median tatasusunan tidak tertib dalam PHP tanpa mengubah susunan tatasusunan? Mari kita lihat di bawah.

1. Gunakan isihan pantas untuk mencari median

Algoritma isihan pantas ialah algoritma isihan berasaskan perbandingan dan kerumitan masanya dalam kes purata ialah O(nlogn) , dan tidak memerlukan ruang memori tambahan. Oleh itu, kita boleh menggunakan isihan pantas untuk mengisih tatasusunan dan mencari median.

Idea utama algoritma isihan pantas ialah memilih elemen penanda aras dalam tatasusunan, dan kemudian membahagi tatasusunan kepada dua bahagian, satu bahagian mengandungi semua nilai kurang daripada elemen penanda aras, dan bahagian lain mengandungi semua nilai yang lebih besar daripada elemen penanda aras. Kedua-dua bahagian ini kemudiannya diisih secara rekursif sehingga keseluruhan tatasusunan diisih.

Untuk mencari median tatasusunan tidak tertib, kita boleh mengisihnya terlebih dahulu menggunakan algoritma isihan cepat, dan kemudian menentukan median berdasarkan panjang tatasusunan yang diisih.

Berikut ialah contoh kod PHP yang menggunakan isihan pantas untuk mencari median:

function quickSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $pivot = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for($i=1; $i<$len; $i++){
        if($arr[$i] <= $pivot){
            $left_arr[] = $arr[$i];
        }else{
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quickSort($left_arr);
    $right_arr = quickSort($right_arr);
    return array_merge($left_arr, array($pivot), $right_arr);
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
$sorted_arr = quickSort($arr);
$len = count($sorted_arr);
if($len % 2 == 0){
    $middle = ($sorted_arr[$len/2-1] + $sorted_arr[$len/2])/2;
}else{
    $middle = $sorted_arr[($len-1)/2];
}
echo "中数为：".$middle;

2. Menggunakan isihan timbunan untuk mencari median

Algoritma isihan timbunan ialah Algoritma isihan untuk struktur data pokok berasaskan timbunan. Dalam isihan timbunan, kami mengisih tatasusunan dengan membina timbunan maks atau timbunan min. Kita boleh menggunakan timbunan maks untuk mencari median tatasusunan tidak tertib.

Timbunan maks ialah pokok binari yang memenuhi sifat berikut:

1 Nilai setiap nod timbunan adalah lebih besar daripada atau sama dengan nilai nod anak kiri dan kanannya.

2. Timbunan sentiasa pokok binari yang lengkap.

Untuk tatasusunan tidak tertib, kita boleh mengisihnya dengan membina timbunan maksimum. Kemudian, kita boleh mencari median berdasarkan sifat timbunan maksimum.

Berikut ialah contoh kod PHP yang menggunakan isihan timbunan untuk mencari median:

function buildMaxHeap(&$arr, $index, $heapSize){
    $left = 2*$index+1;
    $right = 2*$index+2;
    $max = $index;
    if($left<$heapSize && $arr[$left]>$arr[$max]){
        $max = $left;
    }
    if($right<$heapSize && $arr[$right]>$arr[$max]){
        $max = $right;
    }
    if($max != $index){
        $temp = $arr[$index];
        $arr[$index] = $arr[$max];
        $arr[$max] = $temp;
        buildMaxHeap($arr, $max, $heapSize);
    }
}

function heapSort(&$arr){
    $heapSize = count($arr);
    for($i=intval($heapSize/2)-1; $i>=0; $i--){
        buildMaxHeap($arr, $i, $heapSize);
    }
    for($i=$heapSize-1; $i>=1; $i--){
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        $heapSize--;
        buildMaxHeap($arr, 0, $heapSize);
    }
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
heapSort($arr);
$len = count($arr);
if($len % 2 == 0){
    $middle = ($arr[$len/2-1] + $arr[$len/2])/2;
}else{
    $middle = $arr[($len-1)/2];
}
echo "中数为：".$middle;

Ringkasan

Di atas ialah dua kaedah mencari median dalam tatasusunan tidak tertib dalam PHP . Walaupun kerumitan masa mereka berbeza, mereka semua boleh melaksanakan fungsi menyusun tatasusunan tidak tertib dengan cepat dan mencari median. Jika anda perlu mengisih sejumlah besar tatasusunan tidak tertib dan mencari median, adalah disyorkan agar anda menggunakan algoritma isihan timbunan, yang mempunyai prestasi kerumitan masa yang lebih baik.

Atas ialah kandungan terperinci Bagaimana untuk mencari median daripada tatasusunan tidak tertib dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!