leetcode179最大数怎么用php实现

题目描述：

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

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

示例 2:

立即学习“PHP免费学习笔记（深入）”；

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

解题思路：

这道题目是一道简单的排序问题，但是需要对于排序的比较方式进行一定的改变，因为我们需要形成的是最大值，而不是小数，所以我们需要改变一下排序的方式。

我们可以将两个数字拼接在一起，比较两个数字拼接起来的大小，如果 A + B > B + A，那么我们就认为 A 的权值比 B 要大。比如 2 和 10，2 + 10 = 210，10 + 2 = 102，我们就可以确定 2 的权值比 10 大。

具体的算法实现，我们可以使用快速排序的方式进行排序，每次在分割数组时，我们判断比较的方式，保证形成的拼接起来最大的数。

代码实现：

Programming Helper

AI代码自动生成器，在AI的帮助下更快地编程

下载

<?php

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)，使用的排序算法是快速排序。在排序时，我们使用的比较方法是比较字符串形式的拼接结果，保证最终形成的数值是最大的。