요소를 교환하여 사전식으로 가장 작은 배열 만들기

2948. 요소를 교환하여 사전식으로 가장 작은 배열 만들기

난이도:중

주제: 배열, 결합 찾기, 정렬

0-인덱스 양수 정수 배열과 양수 제한이 제공됩니다.

한 번의 작업으로 두 개의 인덱스 i와 j를 선택하고 nums[i]와 nums[j]를 교환할 수 있습니다. if |nums[i] - nums[j]|

연산을 여러 번 수행하여 얻을 수 있는 사전식으로 가장 작은 배열을 반환합니다.

a와 b가 다른 첫 번째 위치에서 배열 a의 요소가 b의 해당 요소보다 작은 경우 배열 a는 배열 b보다 사전순으로 작습니다. 예를 들어, 배열 [2,10,3]은 배열 [10,2,3]보다 사전순으로 더 작습니다. 왜냐하면 인덱스 0과 2

예 1:

• 입력: 숫자 = [1,5,3,9,8], 제한 = 2
• 출력: [1,3,5,8,9]
• 설명: 작업을 2번 적용합니다.
  숫자[1]을 숫자[2]로 바꿉니다. 배열은 [1,3,5,9,8]
  • 이 됩니다.
  숫자[3]을 숫자[4]로 바꿉니다. 배열은 [1,3,5,8,9]
  • 가 됩니다.
  더 이상 연산을 적용해도 사전순으로 더 작은 배열을 얻을 수 없습니다.
  다른 작업을 수행해도 동일한 결과를 얻을 수도 있습니다.

예 2:

• 입력: 숫자 = [1,7,6,18,2,1], 제한 = 3
• 출력: [1,6,7,18,1,2]
• 설명: 작업을 3번 적용합니다.
  숫자[1]을 숫자[2]로 바꿉니다. 배열은 [1,6,7,18,2,1]
  • 이 됩니다.
  숫자[0]을 숫자[4]로 바꿉니다. 배열은 [2,6,7,18,1,1]
  • 이 됩니다.
  숫자[0]을 숫자[5]로 바꿉니다. 배열은 [1,6,7,18,1,2]
  • 가 됩니다.
  더 이상 연산을 적용해도 사전순으로 더 작은 배열을 얻을 수 없습니다.

예 3:

• 입력: 숫자 = [1,7,28,19,10], 제한 = 3
• 출력: [1,7,28,19,10]
• 설명: [1,7,28,19,10]은 두 인덱스에 연산을 적용할 수 없기 때문에 얻을 수 있는 사전식으로 가장 작은 배열입니다.

예 4:

• 입력: 숫자 = [1,60,34,84,62,56,39,76,49,38], 제한 = 4
• 출력: [1,56,34,84,60,62,38,76,49,39]

제약조건:

1 5 1 9 1 9

힌트:

1. nums의 모든 요소가 노드이고 조건을 만족하는 쌍이 그 사이에 간선을 갖는 가상 그래프를 구성합니다.
2. 모든 모서리를 구성하는 대신 연결된 구성요소에만 관심을 둡니다.
3. DSU를 사용할 수 있나요?
4. 숫자를 정렬합니다. 이제 연속된 요소에 모서리가 있는지 고려하여 동일한 연결된 구성요소에 속하는지 확인하면 됩니다. 따라서 연결된 모든 구성 요소는 정렬 후 위치 연속 요소의 목록이 됩니다.
5. 0에서 nums.length - 1까지의 각 숫자 인덱스에 대해 연결된 구성 요소에 있는 현재 최소값으로 변경하고 연결된 구성 요소에서 해당 값을 제거할 수 있습니다.

해결책:

문제는 조건에 따라 배열의 요소를 교환하여 사전순으로 가장 작은 배열을 찾도록 요구합니다. 특히 두 요소 nums[i]와 nums[j] 사이의 절대 차이(|nums[i] - nums[j]|)가 주어진 제한보다 작거나 같은 경우에만 교체할 수 있습니다.

핵심사항

1. 사전순서: 배열 a는 첫 번째 다른 인덱스에서 a[i]
2. 교환 조건: 교환되는 숫자의 차이가 ≤ 제한인 경우에만 교환이 허용됩니다.
3. 효율적인 그룹화: DSU(Disjoint Set Union) 또는 정렬 기술을 사용하여 유효한 스왑으로 연결된 요소를 그룹화할 수 있습니다.
4. 최적 배열: 각 그룹에 대해 가장 작은 순서가 되도록 인덱스와 값을 정렬합니다.

접근방법

1. 그룹 구성: 배열을 유효한 스왑이 가장자리를 정의하는 가상 그래프로 처리합니다. 정렬을 사용하여 연결된 그룹을 식별하거나 DSU를 사용하여 인덱스를 효율적으로 그룹화하세요.
2. 그룹 정렬: 연결된 인덱스의 각 그룹 내에서 요소를 사전순으로 재배열합니다.
3. 출력 구성: 정렬된 값을 다시 해당 위치에 배치합니다.

계획

1. (값, 인덱스) 쌍을 추출하고 값별로 정렬하면 효율적인 그룹 검색이 가능합니다.
2. 정렬된 값을 반복하여 한계 조건에 따라 연결된 인덱스 그룹을 형성합니다.
3. 각 그룹의 경우:
   • 색인과 값을 독립적으로 정렬합니다.
   • 사전순으로 원래 위치에 값을 다시 할당합니다.
4. 수정된 배열을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2948. 요소를 교환하여 사전식으로 가장 작은 배열 만들기

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

/**
 * @param $nums
 * @return array
 */
function getNumAndIndexes($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1, 5, 3, 9, 8];
$limit1 = 2;
print_r(lexicographicallySmallestArray($nums1, $limit1)); // Output: [1, 3, 5, 8, 9]

$nums2 = [1, 7, 6, 18, 2, 1];
$limit2 = 3;
print_r(lexicographicallySmallestArray($nums2, $limit2)); // Output: [1, 6, 7, 18, 1, 2]

$nums3 = [1, 7, 28, 19, 10];
$limit3 = 3;
print_r(lexicographicallySmallestArray($nums3, $limit3)); // Output: [1, 7, 28, 19, 10]

$nums4 = [1, 60, 34, 84, 62, 56, 39, 76, 49, 38];
$limit4 = 4;
print_r(lexicographicallySmallestArray($nums4, $limit4)); // Output: [1, 56, 34, 84, 60, 62, 38, 76, 49, 39]
?>

설명:

1. 추출 및 정렬(getNumAndIndexes):

   쉬운 참조를 위해 값과 지수를 쌍으로 결합하십시오 연결된 구성 요소의 효율적인 그룹화를 가능하게하기 위해 값별로 쌍을 정렬합니다.
   그룹화 로직 :
   정렬 된 쌍을 가로 지르십시오. 연속 값의 차이가 ≤ 한계 인 경우 동일한 그룹에 추가하십시오. 그렇지 않으면 새 그룹을 시작하십시오.

2. 정렬 및 재 할당 :

   각 그룹의 <:> :
   지수와 값을 추출하십시오 가장 작은 값이 가장 작은 지수에 배치되도록 두 목록을 정렬하십시오. 정답 배열에서 정렬 된 값을 해당 위치에 재 할당합니다.

3. 결과 구조 : 모든 그룹을 처리 한 후 업데이트 된 배열을 반환합니다

   • 예제 연습
     예 1
     • 입력 : nums = [1,5,3,9,8], 한계 = 2
     추출 및 정렬 :
   쌍 : [(1, 0), (5, 1), (3, 2), (9, 3), (8, 4)]
   분류 된 쌍 : [(1, 0), (3, 2), (5, 1), (8, 4), (9, 3)]

4. 그룹화 :

   그룹 1 : [(1, 0)]
   그룹 2 : [(3, 2), (5, 1)]
   • 그룹 3 : [(8, 4), (9, 3)]

분류 그룹 : 그룹 1 : 변경 없음 ([1]) 그룹 2 : values ​​= [3, 5], indices = [1, 2] → 결과 : [1, 3, 5] 그룹 3 : value = [8, 9], indices = [3, 4] → 결과 : [8, 9]

최종 결과 : [1, 3, 5, 8, 9]

1. 시간 복잡성

   정렬 : NUMS 배열을 정렬하면
   o (n log n)
   그룹화 :
   • 정렬 된 배열을 통한 선형 순회 o (n)
   .
<:> 정렬 그룹 : 각 그룹의 분류 지수 및 값은

2. o (k log k) 를 가져갑니다. 그룹 규모입니다. 모든 그룹에 걸쳐 합산하면

   o (n log n)
   . 입니다
   • 전체 시간 복잡성 :
   • o (n log n)
   예제의 출력

3. 예 2 입력 : nums = [1,7,6,18,2,1], 한계 = 3 출력 :

   [1,6,7,18,1,2]
   예 3
   • 입력 : nums = [1,7,28,19,10], 한계 = 3
   • 출력 :
   [1,7,28,19,10] 이 접근법은 정렬을 사용하여 연결된 구성 요소와 각 구성 요소 내에서 값을 재 배열하여 어휘에 가장 작은 배열을 달성함으로써 문제를 효율적으로 처리합니다. 분류 및 그룹 처리를 활용하여
   • 복잡성으로 최적의 솔루션을 보장합니다.
   연락처 링크

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

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

   • 링크드인
   • 깃허브

위 내용은 요소를 교환하여 사전식으로 가장 작은 배열 만들기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!