632. K 목록에서 가장 작은 범위를 덮는 요소

난이도 : hard

주제 : 배열, 해시 테이블, 탐욕, 슬라이딩 창, 정렬, 힙 (우선 큐)

비정치 주문 의 k 목록이 있습니다. 각각의 k 목록에서 하나 이상의 숫자를 포함하는 가장 작은 범위를 찾으십시오.

우리는 [a, b] 범위가 범위 [c, d]보다 작습니다. b -a 또는 a

예 1 :

• 입력 : nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
• 출력 : [20,24]
• 설명:
  • 목록 1 : [4, 10, 15, 24,26], 24는 [20,24] 범위에 있습니다.
  • 목록 2 : [0, 9, 12, 20], 20은 범위 [20,24]입니다.
  • 목록 3 : [5, 18, 22, 30], 22는 [20,24] 범위에 있습니다.

예 2 :

• 입력 : nums = [[1,2,3], [1,2,3], [1,2,3]]
• 출력 : [1,1]

제약 조건 :

• nums.length == k
• 1
• 1
• -10 ⁵ 5
• Nums [i]는 비정치를 제거하지 않는 순서로 정렬됩니다.

해결책:

우리는 min-heap (또는 우선 순위 큐)을 사용하여 각 목록에서 슬라이딩 창을 유지하기 위해 각 목록에서 가장 작은 요소를 추적하여 각 목록에서 하나 이상의 요소를 포함하는 가장 작은 범위를 찾을 수 있습니다.

접근하다

1. Min-Heap 초기화 ​​ : Min-Heap을 사용하여 각 K 목록에서 현재 요소를 저장합니다. 각 힙 항목은 값, 목록의 인덱스 및 해당 목록의 요소 인덱스를 포함하는 튜플입니다.
2. 최대 값 추적 : 현재 창의 최대 값을 추적합니다. 이는 범위가 가장 작은 요소 (힙에서)와 현재 최대 값의 차이에 의해 결정되기 때문에 중요합니다.
3. 목록 끝까지 반복 : 각 반복에 대해 :
   • 힙에서 최소 요소를 추출합니다.
   • 현재 범위 [min_value, max_value]가 이전에 기록 된 가장 작은 범위보다 작 으면 범위를 업데이트합니다.
   • 최소 요소가 취한 목록의 다음 요소로 이동합니다. 최대 값을 업데이트하고 새 요소를 힙에 추가하십시오.
4. 종료 : 프로세스는 목록이 소진 될 때 종료됩니다.

PHP 에서이 솔루션을 구현하겠습니다 : 632. K 목록에서 가장 작은 범위를 덮는 요소

설명:

1. 힙 초기화 :
   • 초기 힙에는 각 목록의 첫 번째 요소가 포함되어 있습니다. 우리는 또한 첫 번째 요소들 사이에서 최대 요소를 추적합니다.
2. 힙 처리 :
   • 힙에서 최소 요소를 추출한 다음 같은 목록에서 다음 요소를 추가하여 범위를 확장하십시오 (사용 가능한 경우).
   • 힙에 새 요소를 추가 한 후 새 요소가 더 큰 경우 MaxValue를 업데이트하십시오.
   • MaxValue와 MinValue의 차이가 이전에 기록 된 범위보다 작을 때마다 가장 작은 범위를 업데이트합니다.
3. 종료:
   • 루프는 더 이상 범위에 모든 목록을 포함시킬 수 없으므로 어떤 목록이 요소가 실행될 때 중지됩니다.

복잡성 분석

• 시간 복잡성 : o (n * log k), 여기서 n은 모든 목록의 총 요소 수이고 k는 목록 수입니다. 복잡성은 힙에서 요소를 삽입하고 제거함으로써 발생합니다.
• 공간 복잡성 : O (k) 힙에 요소를 저장합니다.

이 솔루션은 각각의 K 정렬 목록에서 하나 이상의 숫자를 포함하는 가장 작은 범위를 효율적으로 찾습니다.

연락처 링크

이 시리즈가 도움이된다면 리포지토리 Github의 스타를 제공하거나 좋아하는 소셜 네트워크에 게시물을 공유하는 것이 좋습니다. 당신의 지원은 나에게 큰 의미가 있습니다!

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

• linkedin
• github