Bagaimana untuk melaksanakan nombor maksimum leetcode179 menggunakan php

Perihalan masalah:

Memandangkan satu set integer bukan negatif, susun semula tertibnya untuk membentuk integer terbesar.

Contoh 1:

Input: [10,2]
Output: 210

Contoh 2:

Input: [3,30, 34,5,9]
Output: 9534330
Nota: Hasil output mungkin sangat besar, jadi anda perlu mengembalikan rentetan dan bukannya integer.

Idea penyelesaian masalah:

Soalan ini adalah masalah pengisihan yang mudah, tetapi ia memerlukan perubahan tertentu dalam kaedah pengisihan perbandingan, kerana yang perlu kita bentuk adalah nilai maksimum, bukan decimal , jadi kita perlu menukar cara pengisihan.

Kita boleh sambung dua nombor dan bandingkan saiz dua nombor yang disambung bersama-sama. Jika A + B > Sebagai contoh, 2 dan 10, 2 + 10 = 210, 10 + 2 = 102, kita boleh menentukan bahawa berat 2 lebih besar daripada 10.

Untuk pelaksanaan algoritma khusus, kami boleh menggunakan isihan pantas untuk mengisih Setiap kali kami membahagikan tatasusunan, kami menilai kaedah perbandingan untuk memastikan nombor terbesar terbentuk apabila disambung bersama.

Pelaksanaan kod:

Penyelesaian kelas {

/**
 * @param Integer[] $nums
 * @return String
 */
function largestNumber($nums) {
    if (empty($nums)) {
        return '';
    }

    $this->quickSort($nums, 0, count($nums) - 1);

    $result = implode('', $nums);

    return $result[0] == '0' ? '0' : $result;
}

function quickSort(&$nums, $left, $right) {
    if ($left >= $right) {
        return;
    }

    $mid = $this->partition($nums, $left, $right);

    $this->quickSort($nums, $left, $mid - 1);
    $this->quickSort($nums, $mid + 1, $right);
}

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

    for ($j = $left; $j < $right; $j++) {
        if ($this->cmp($nums[$j], $pivot) > 0) {
            $i++;
            $this->swap($nums, $i, $j);
        }
    }

    $i++;
    $this->swap($nums, $i, $right);

    return $i;
}

function swap(&$nums, $i, $j) {
    $tmp = $nums[$i];
    $nums[$i] = $nums[$j];
    $nums[$j] = $tmp;
}

function cmp($a, $b) {
    return strval($a) . strval($b) > strval($b) . strval($a) ? 1 : - 1;
}

}
$solution = new Solution( );
$nums1 = [10, 2];
$result1 = $solution->largestNumber($nums1);
print('Result 1: ' . $result1 . "n ");
$nums2 = [3, 30, 34, 5, 9];
$result2 = $solution->largestNumber($nums2);
print('Hasil 2: ' . $result2 . "n");
?>
Kesimpulan: 
Kerumitan masa bagi soalan ini ialah O(nlogn), dan algoritma pengisihan yang digunakan ialah Isih Pantas. Semasa menyusun, kaedah perbandingan yang kami gunakan ialah membandingkan hasil penyambungan dalam bentuk rentetan untuk memastikan nilai akhir adalah yang terbesar. 
Atas ialah kandungan terperinci Bagaimana untuk melaksanakan nombor maksimum leetcode179 menggunakan php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!