Comment implémenter le nombre maximum de leetcode179 en utilisant php

Description du problème :

Étant donné un ensemble d'entiers non négatifs, réorganisez leur ordre pour former le plus grand entier.

Exemple 1 :

Entrée : [10,2]
Sortie : 210

Exemple 2 :

Entrée : [3,30,34,5,9]
Sortie : 9534330
Explication : Le résultat de la sortie peut être very large , vous devez donc renvoyer une chaîne au lieu d'un entier.

Idées de résolution de questions :

Cette question est un problème de tri simple, mais elle nécessite certains changements dans la méthode de tri par comparaison, car ce que nous devons former est la valeur maximale, pas une décimale, nous devons donc changer la Méthode de tri.

Nous pouvons assembler deux nombres et comparer la taille des deux nombres. Si A + B > B + A, alors nous pensons que le poids de A est supérieur à celui de B. Par exemple, 2 et 10, 2 + 10 = 210, 10 + 2 = 102, on peut déterminer que le poids de 2 est supérieur à 10.

Pour l'implémentation spécifique de l'algorithme, nous pouvons utiliser le tri rapide. Chaque fois que nous divisons le tableau, nous jugeons la méthode de comparaison pour garantir que le plus grand nombre est formé lorsqu'il est assemblé.

Implémentation du code :

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-> mostNumber($nums1);
print('Résultat 1 : ' . $result1 . "n");
$nums2 = [3, 30, 34, 5, 9];
$result2 = $solution->largestNumber ($nums2);
print('Result 2: ' . $result2 . "n");
?>
Conclusion : 
La complexité temporelle de cette question est O(nlogn), et l'algorithme de tri utilisé est un tri rapide. Lors du tri, la méthode de comparaison que nous utilisons consiste à comparer les résultats d'épissage sous forme de chaînes pour garantir que la valeur finale est la plus grande. 
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!