K 곱셈 연산 후의 최종 배열 상태 I

3264. K 곱셈 연산 후의 최종 배열 상태 I

난이도: 쉬움

주제: 배열, 수학, 힙(우선순위 큐), 시뮬레이션

정수 배열 nums, 정수 k 및 정수 승수가 제공됩니다.

숫자에 대해 k 연산을 수행해야 합니다. 각 작업에서:

• 숫자에서 최소값 x를 찾습니다. 최소값이 여러 번 나타나는 경우 먼저 나타나는 값을 선택하세요.
• 선택한 최소값 x를 x * 승수로 바꿉니다.

모든 k 연산을 수행한 후 nums의 최종 상태를 나타내는 정수 배열을 반환합니다.

예 1:

• 입력: nums = [2,1,3,5,6], k = 5, 승수 = 2
• 출력: [8,4,6,5,6]
• 설명:

| 운영 | 결과 |
|------|----|
| 작업 1 후 | [2, 2, 3, 5, 6] |
| 작업 2 후 | [4, 2, 3, 5, 6] |
| 작업 3 후 | [4, 4, 3, 5, 6] |
| 작업 4 후 | [4, 4, 6, 5, 6] |
| 작업 5 후 | [8, 4, 6, 5, 6] |

예 2:

• 입력: nums = [1,2], k = 3, 승수 = 4
• 출력: [16,8]
• 설명:

| 운영 | 결과 |
|------|----|
| 작업 1 후 | [2, 2, 3, 5, 6] |
| 작업 2 후 | [4, 2, 3, 5, 6] |
| 작업 3 후 | [4, 4, 3, 5, 6] |
| 작업 4 후 | [4, 4, 6, 5, 6] |
| 작업 5 후 | [8, 4, 6, 5, 6] |

제약조건:

• 1
• 1
• 1
• 1

힌트:

1. 우선순위 대기열에서 정렬된 쌍(nums[index], index)을 유지합니다.
2. K번 동작을 시뮬레이션합니다.

해결책:

문제 설명에 설명된 대로 작업을 구현해야 합니다. 핵심 단계는 배열에서 최소값을 찾아 주어진 승수를 곱한 값으로 바꾼 다음 이 과정을 k번 반복하는 것입니다.

첫 번째 최소값 발생을 선택하고 교체해야 한다는 점을 고려하면 각 작업 중에 최소값 인덱스를 추적하여 이에 접근할 수 있습니다. PHP 구현은 우선순위 큐(최소 힙)를 사용하여 각 작업 중에 최소값을 효율적으로 검색하고 업데이트합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3264. K 곱셈 연산 후의 최종 배열 상태 I

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $multiplier
 * @return Integer[]
 */
function finalArrayState($nums, $k, $multiplier) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test Case 1
$nums1 = [2, 1, 3, 5, 6];
$k1 = 5;
$multiplier1 = 2;
$result1 = finalArrayState($nums1, $k1, $multiplier1);
echo "Output: [" . implode(", ", $result1) . "]\n";

// Test Case 2
$nums2 = [1, 2];
$k2 = 3;
$multiplier2 = 4;
$result2 = finalArrayState($nums2, $k2, $multiplier2);
echo "Output: [" . implode(", ", $result2) . "]\n";
?>

설명:

1. 초기화: k개 작업을 수행해야 하므로 k번 반복합니다.
2. 최소값 찾기:
   • nums 배열을 반복하여 가장 작은 값과 첫 번째 발생 인덱스를 찾습니다.
3. 최소값 곱하기:
   • 식별된 인덱스의 값을 현재 값과 승수의 곱으로 바꿉니다.
4. 반복:
   • k회 반복에 대해 위 단계를 반복합니다.
5. 최종 배열 반환:
   • 모든 작업이 끝나면 수정된 배열을 반환합니다.

테스트 출력

제공된 테스트 사례의 경우:

테스트 사례 1:

입력:

$nums = [2, 1, 3, 5, 6];
$k = 5;
$multiplier = 2;

출력:

Output: [8, 4, 6, 5, 6]

테스트 사례 2:

입력:

$nums = [1, 2];
$k = 3;
$multiplier = 4;

출력:

Output: [16, 8]

복잡성

1. 시간 복잡성:

   • k개의 연산 각각에 대해 배열의 최소값을 찾으려면 O(n)이 필요합니다.
   • 전체: O(k x n), 여기서 n은 배열의 크기입니다.

2. 공간 복잡성:

   • 이 솔루션은 O(1) 추가 공간
   을 사용합니다.

이 솔루션은 제약 조건을 준수하며 모든 테스트 사례에 대해 예상되는 결과를 제공합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 K 곱셈 연산 후의 최종 배열 상태 I의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!