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

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 < 10.

예 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 <= nums.length <= 10
• 5
1 <= 숫자[i] <= 10
• 9
1 <= 제한 <= 10
• 9

힌트:

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

해결책:

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

핵심사항

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

접근방법

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

계획

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

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

  
  
  설명:




추출 및 정렬(getNumAndIndexes):

 쉬운 참조를 위해 값과 지수를 쌍으로 결합하십시오
 연결된 구성 요소의 효율적인 그룹화를 가능하게하기 위해 값별로 쌍을 정렬합니다.



  그룹화 로직 :  



 정렬 된 쌍을 가로 지르십시오. 연속 값의 차이가 ≤ 한계 인 경우 동일한 그룹에 추가하십시오. 그렇지 않으면 새 그룹을 시작하십시오. 




  정렬 및 재 할당 :  


각 그룹의 <:> :


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







  결과 구조 :  


모든 그룹을 처리 한 후 업데이트 된 배열을 반환합니다





  
  
   예제 연습 



  
  
  예 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)]





  그룹화 :  


 그룹 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] 
 




  
  
   시간 복잡성 




 정렬 :  NUMS 배열을 정렬하면 
  o (n log n)  


 그룹화 : 
 정렬 된 배열을 통한 선형 순회  o (n)  
. 

<:> 정렬 그룹 :  각 그룹의 분류 지수 및 값은 
 
 o (k log k)  를 가져갑니다. 그룹 규모입니다. 모든 그룹에 걸쳐 합산하면 
 
 o (n log n) 
 
. 입니다


  전체 시간 복잡성 :  
 
 o (n log n)  
 


  
  
   예제의 출력 




  
  
  예 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!