3264. K 곱셈 작업 후 최종 배열 상태 I

난이도 : 쉬운

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

정수 배열 번호, 정수 K 및 정수 승수가 주어집니다.

NUM에서 K 작업을 수행해야합니다. 각 작업에서 :

• Nums에서 최소값 x를 찾으십시오. 최소 값의 여러 발생이있는 경우 첫 번째 값을 선택하십시오 .
.
• 선택한 최소값 X를 X * Multiplier로 교체합니다.

return 모든 k 작동을 수행 한 후 NUM의 최종 상태를 나타내는 정수 배열

예 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, multiplier = 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 Times.

해결책:

문제 설명에 설명 된대로 작업을 구현해야합니다. 주요 단계는 배열에서 최소값을 찾고 주어진 승수로 곱한 값으로 바꾸고이 프로세스 k 시간을 반복하는 것입니다.

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

PHP 에서이 솔루션을 구현하겠습니다 : 3264. k 곱셈 작업 후 최종 배열 상태 i

설명:

1. 초기화 : k 작업을 수행해야하므로 Loop K Times.
2. 최소값 찾기 :
   • 가장 작은 값과 그 첫 번째 발생 색인 .
   를 찾기 위해 배열 번호를 반복합니다.
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의 스타를 제공하거나 좋아하는 소셜 네트워크에 게시물을 공유하는 것이 좋습니다. 당신의 지원은 나에게 큰 의미가 있습니다!

이와 같은 유용한 컨텐츠를 원한다면 언제든지 나중하십시오 :

• linkedin
• github