How to implement leetcode179 maximum number using php

Title description:

Given a set of non-negative integers, rearrange their order to form the largest integer.

Example 1:

Input: [10,2]
Output: 210

Example 2:

Input: [3,30, 34,5,9]
Output: 9534330
Note: The output result may be very large, so you need to return a string instead of an integer.

Question-solving ideas:

This question is a simple sorting problem, but it requires certain changes in the comparison method of sorting, because what we need to form is the maximum value, not a decimal. , so we need to change the way of sorting.

We can splice two numbers together and compare the size of the two numbers spliced ​​together. If A B > B A, then we think that the weight of A is greater than that of B. For example, 2 and 10, 2 10 = 210, 10 2 = 102, we can determine that the weight of 2 is greater than 10.

For the specific algorithm implementation, we can use quick sort to sort. Every time we divide the array, we judge the comparison method to ensure that the largest number is formed when spliced ​​together.

Code implementation:

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");
?>
Conclusion:
The time complexity of this question is O(nlogn), and the sorting algorithm used is Quick sort. When sorting, the comparison method we use is to compare the splicing results in the form of strings to ensure that the final value is the largest. 
The above is the detailed content of How to implement leetcode179 maximum number using php. For more information, please follow other related articles on the PHP Chinese website!