首页  >  文章  >  后端开发  >  leetcode179最大数怎么用php实现

leetcode179最大数怎么用php实现

PHPz
PHPz原创
2023-04-19 10:04:59369浏览

题目描述:

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

示例 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中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn