PHP를 사용하여 leetcode179 최대 개수를 구현하는 방법

문제 설명:

음수가 아닌 정수 집합이 주어지면 순서를 재정렬하여 가장 큰 정수를 형성하세요.

예 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 솔루션 {

/**
 * @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-> maximumNumber($nums1);
print('결과 1: ' . $result1 . "n");
$nums2 = [3, 30, 34, 5, 9];
$result2 = $solution->largestNumber ($nums2);
print('Result 2: ' . $result2 . "n");
?>
결론: 
이 질문의 시간 복잡도는 O(nlogn)이며, 정렬 알고리즘이 사용되었습니다. 퀵 정렬이다. 정렬할 때 우리가 사용하는 비교 방법은 접합 결과를 문자열 형태로 비교하여 최종 값이 가장 큰지 확인하는 것입니다. 
위 내용은 PHP를 사용하여 leetcode179 최대 개수를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!