PHPを使用してleetcode179の最大数を実装する方法

タイトルの説明:

負でない整数のセットが与えられた場合、その順序を並べ替えて最大の整数を形成します。

例 1:

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

例 2:

入力: [3,30, 34,5,9]
出力: 9534330
注: 出力結果は非常に大きくなる可能性があるため、整数ではなく文字列を返す必要があります。

質問解決のアイデア:

この質問は単純な並べ替え問題ですが、形成する必要があるのは最大値であり、最大値であるため、並べ替えの比較方法に特定の変更が必要です。 10 進数なので、並べ替え方法を変更する必要があります。

2 つの数値を結合し、結合した 2 つの数値の大きさを比較できます。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('結果 1: ' . $result1 . "\n" );
$nums2 = [3, 30, 34, 5, 9];
$result2 = $solution->largestNumber($nums2);
print('結果 2: ' . $result2 . "\n");
?>
結論:
この質問の時間計算量は O(nlogn) であり、使用される並べ替えアルゴリズムクイックソートです。並べ替えの際に使用する比較方法は、文字列の形式でスプライシング結果を比較し、最終的な値が最大であることを確認することです。 
以上がPHPを使用してleetcode179の最大数を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。