leetcode179最大數怎麼用php實現

題目描述：

給定一組非負整數，重新排列它們的順序使之組成一個最大的整數。

範例1:

輸入: [10,2]
輸出: 210

範例2:

輸入: [3,30, 34,5,9]
輸出: 9534330
說明: 輸出結果可能非常大，所以你需要傳回一個字串而不是整數。

解題思路：

這題目是一道簡單的排序問題，但是需要對於排序的比較方式進行一定的改變，因為我們需要形成的是最大值，而不是小數，所以我們需要改變排序的方式。

我們可以將兩個數字拼接在一起，比較兩個數字拼接起來的大小，如果 A B > B A，那麼我們就認為 A 的權值比 B 大。例如 2 和 10，2 10 = 210，10 2 = 102，我們就可以確定 2 的權值比 10 大。

具體的演算法實現，我們可以使用快速排序的方式進行排序，每次在分割數組時，我們判斷比較的方式，保證形成的拼接起來最大的數。

程式碼實作：

class Solution {

/**
 * @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('Result 2: ' . $result2 . "\n");
?>
#結論：
本題實現的時間複雜度為O(nlogn)，使用的排序演算法是快速排序。在排序時，我們使用的比較方法是比較字串形式的拼接結果，並確保最終形成的數值是最大的。 
以上是leetcode179最大數怎麼用php實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！