. K 목록의 최소 범위 포함 요소

632. K 목록의 최소 범위 포함 요소

난이도:어려움

주제: 배열, 해시 테이블, Greedy, 슬라이딩 윈도우, 정렬, 힙(우선순위 대기열)

내림차순으로 정렬된 k 개의 정수 목록이 있습니다. 각 k개 목록에서 하나 이상의 숫자를 포함하는 가장 작은 범위를 찾습니다.

b - a 또는 a

예 1:

• 입력: 숫자 = [[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:

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

제약조건:

• nums.length == k
• 1
• 1
• -10⁵ 5
• nums[i]는 감소하지 않는 순서
로 정렬됩니다.

해결책:

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

접근하다

1. 최소 힙 초기화: 최소 힙을 사용하여 k개 목록 각각의 현재 요소를 저장합니다. 각 힙 항목은 값, 해당 항목이 나온 목록의 인덱스, 해당 목록에 있는 요소의 인덱스를 포함하는 튜플입니다.
2. 최대 값 추적: 현재 창의 최대 값을 추적합니다. 범위는 힙에서 가장 작은 요소와 현재 최대값 간의 차이에 의해 결정되므로 이는 중요합니다.
3. 목록 끝까지 반복: 각 반복에 대해:
   • 힙에서 최소 요소를 추출합니다.
   • 현재 범위[최소값, 최대값]가 이전에 기록된 최소 범위보다 작은 경우 범위를 업데이트하세요.
   • 최소 요소를 가져온 목록의 다음 요소로 이동합니다. 최대값을 업데이트하고 새 요소를 힙에 추가하세요.
4. 종료: 목록이 소진되면 프로세스가 종료됩니다.

이 솔루션을 PHP로 구현해 보겠습니다. 632. K 목록의 최소 범위 포함 요소

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

// Example usage:
$nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
$result = smallestRange($nums);
print_r($result); // Output: [20, 24]
?>

설명:

1. 힙 초기화:
   • 초기 힙에는 각 목록의 첫 번째 요소가 포함됩니다. 또한 첫 번째 요소 중 최대 요소도 추적합니다.
2. 힙 처리:
   • 힙에서 최소 요소를 추출한 후 동일한 목록에서 다음 요소를 추가하여 범위를 확장해 보세요(가능한 경우).
   • 힙에 새 요소를 추가한 후 새 요소가 더 크면 maxValue를 업데이트하세요.
   • maxValue와 minValue의 차이가 이전에 기록된 범위보다 작을 때마다 가장 작은 범위를 업데이트합니다.
3. 해지:
   • 더 이상 범위에 모든 목록을 포함할 수 없으므로 목록에 요소가 부족하면 루프가 중지됩니다.

복잡성 분석

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

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

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 . K 목록의 최소 범위 포함 요소의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!