So implementieren Sie die maximale Anzahl von Leetcode179 mit PHP

Problembeschreibung:

Ordnen Sie bei einer gegebenen Menge nicht negativer Ganzzahlen deren Reihenfolge neu, um die größte Ganzzahl zu bilden.

Beispiel 1:

Eingabe: [10,2]
Ausgabe: 210

Beispiel 2:

Eingabe: [3,30,34,5,9]
Ausgabe: 9534330
Erläuterung: Das Ausgabeergebnis kann sein sehr groß, daher müssen Sie eine Zeichenfolge anstelle einer Ganzzahl zurückgeben.

Ideen zur Lösung von Fragen:

Diese Frage ist ein einfaches Sortierproblem, erfordert jedoch bestimmte Änderungen in der Vergleichsmethode der Sortierung, da wir den Maximalwert und keine Dezimalzahl bilden müssen. Daher müssen wir den Wert ändern Sortiermethode.

Wir können zwei Zahlen zusammenfügen und die Größe der beiden Zahlen vergleichen. Wenn A + B > B + A, dann denken wir, dass das Gewicht von A größer ist als das von B. Zum Beispiel 2 und 10, 2 + 10 = 210, 10 + 2 = 102, wir können feststellen, dass das Gewicht von 2 größer als 10 ist.

Für die spezifische Algorithmusimplementierung können wir die Schnellsortierung zum Sortieren verwenden. Jedes Mal, wenn wir das Array teilen, beurteilen wir die Vergleichsmethode, um sicherzustellen, dass beim Zusammenfügen die größte Zahl gebildet wird.

Code-Implementierung:

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('Ergebnis 1: ' . $result1 . "n");
$nums2 = [3, 30, 34, 5, 9];
$result2 = $solution->largestNumber ($nums2);
print('Result 2: ' . $result2 . "n");
?>
Schlussfolgerung: 
Die zeitliche Komplexität dieser Frage beträgt O(nlogn) und der verwendete Sortieralgorithmus ist Schnellsortierung. Beim Sortieren verwenden wir die Vergleichsmethode, die Spleißergebnisse in Form von Zeichenfolgen zu vergleichen, um sicherzustellen, dass der Endwert der größte ist. 
Das obige ist der detaillierte Inhalt vonSo implementieren Sie die maximale Anzahl von Leetcode179 mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!