>  기사  >  웹 프론트엔드  >  배열에서 K번째로 큰 요소

배열에서 K번째로 큰 요소

Mary-Kate Olsen
Mary-Kate Olsen원래의
2024-09-24 06:16:01397검색

Kth Largest Element in an Array

#️⃣ 배열, 우선순위 대기열, 빠른 선택

https://leetcode.com/problems/kth-largest-element-in-an-array/description

? 문제 이해

배열이 [8, 6, 12, 9, 3, 4]이고 k가 2인 경우 이 배열에서 두 번째로 큰 요소를 찾아야 합니다. 먼저 배열을 정렬합니다: [3, 4, 6, 8, 9, 12] 두 번째로 큰 요소이므로 출력은 9가 됩니다.

✅ 무차별 대입

var findKthLargest = function(nums, k) {
    // Sort the array in ascending order
    nums.sort((a, b) => a - b);

    // Return the kth largest element
    return nums[nums.length - k];
};

설명:

  1. 배열 정렬: 정렬 방법을 사용하여 배열을 오름차순으로 정렬합니다.
  2. k번째로 큰 요소 찾기: k번째로 큰 요소는 인덱스 nums.length - k의 요소에 액세스하여 찾습니다.

시간 복잡도:

  • 정렬: 배열 정렬의 시간 복잡도는 (O(nlog n))입니다. 여기서 (n)은 배열의 길이입니다.
  • 요소 액세스: 배열의 요소에 액세스하는 것은 O(1)입니다.

그러므로 전체 시간 복잡도는 O(n log n)입니다.

공간 복잡도:

  • 내부 정렬: 정렬 방법은 배열을 제자리에서 정렬하므로 정렬 작업의 공간 복잡도는 O(1)입니다.
  • 전체: 추가 데이터 구조를 사용하지 않으므로 전체 공간 복잡도는 O(1)입니다.

✅ 더 좋음

var findKthLargest = function(nums, k) {
        // Create a min-heap using a priority queue
        let minHeap = new MinPriorityQueue();

        // Add the first k elements to the heap
        for (let i = 0; i < k; i++) {
            //minHeap.enqueue(nums[i]): Adds the element nums[i] to the min-heap.
            minHeap.enqueue(nums[i]);
        }

        // Iterate through the remaining elements
        for (let i = k; i < nums.length; i++) {
            //minHeap.front().element: Retrieves the smallest element in the min-heap without removing it.
            if (minHeap.front().element < nums[i]) {
                // minHeap.dequeue(): Removes the smallest element from the min-heap.
                minHeap.dequeue();
                // Add the current element
                minHeap.enqueue(nums[i]);
            }
        }

        // The root of the heap is the kth largest element
        return minHeap.front().element;
    };

설명:

  1. 초기 배열: [2, 1, 6, 3, 5, 4]
  2. k = 3: 세 번째로 큰 요소를 찾아야 합니다.

1단계: 최소 힙에 처음 k개 요소 추가

  • 2를 추가한 후의 힙: [2]
  • 1을 추가한 후의 힙: [1, 2]
  • 6을 추가한 후의 힙: [1, 2, 6]

2단계: 나머지 요소 반복

  • 현재 요소 = 3

    • 비교 전 힙: [1, 2, 6]
    • 힙에서 가장 작은 요소(minHeap.front().element): 1
    • 비교: 3 > 1
    • Action: 1을 제거하고 3을 추가
    • 업데이트 후 힙: [2, 6, 3]
    • 현재 요소 = 5

      • 비교 전 힙: [2, 6, 3]
      • 힙에서 가장 작은 요소(minHeap.front().element): 2
      • 비교: 5 > 2
      • Action: 2를 제거하고 5를 추가
      • 업데이트 후 힙: [3, 6, 5]
    • 현재 요소 = 4

      • 비교 전 힙: [3, 6, 5]
      • 힙에서 가장 작은 요소(minHeap.front().element): 3
      • 비교: 4 > 3
      • Action: 3개 제거 및 4개 추가
      • 업데이트 후 힙: [4, 6, 5]
    • 마지막 단계: 힙의 루트 반환

      • : [4, 6, 5]
      • 세 번째로 큰 요소: 4(힙의 루트)

      시간 복잡도:

      • 힙 작업: 힙에서 요소를 삽입하고 제거하는 데는 O(log k) 시간이 걸립니다.
      • 전체: 배열의 n개 요소 각각에 대해 이러한 작업을 수행하므로 전체 시간 복잡도는 O(n log k)입니다.

      공간 복잡도:

      • 힙 저장소: 힙은 최대 k개의 요소를 저장하므로 공간 복잡도는 O(k)입니다.

      ✅ 최고

      참고: Leetcode가 빠른 선택을 제한하더라도 이 접근 방식은 대부분의 테스트 사례를 통과하므로 기억해야 합니다

      //Quick Select Algo
      
      function quickSelect(list, left, right, k)
      
         if left = right
            return list[left]
      
         Select a pivotIndex between left and right
      
         pivotIndex := partition(list, left, right, 
                                        pivotIndex)
         if k = pivotIndex
            return list[k]
         else if k < pivotIndex
            right := pivotIndex - 1
         else
            left := pivotIndex + 1
      
      var findKthLargest = function(nums, k) {
          // Call the quickSelect function to find the kth largest element
          return quickSelect(nums, 0, nums.length - 1, nums.length - k);
      };
      
      function quickSelect(nums, low, high, index) {
          // If the low and high pointers are the same, return the element at low
          if (low === high) return nums[low];
      
          // Partition the array and get the pivot index
          let pivotIndex = partition(nums, low, high);
      
          // If the pivot index is the target index, return the element at pivot index
          if (pivotIndex === index) {
              return nums[pivotIndex];
          } else if (pivotIndex > index) {
              // If the pivot index is greater than the target index, search in the left partition
              return quickSelect(nums, low, pivotIndex - 1, index);
          } else {
              // If the pivot index is less than the target index, search in the right partition
              return quickSelect(nums, pivotIndex + 1, high, index);
          }
      }
      
      function partition(nums, low, high) {
          // Choose the pivot element
          let pivot = nums[high];
          let pointer = low;
      
          // Rearrange the elements based on the pivot
          for (let i = low; i < high; i++) {
              if (nums[i] <= pivot) {
                  [nums[i], nums[pointer]] = [nums[pointer], nums[i]];
                  pointer++;
              }
          }
      
          // Place the pivot element in its correct position
          [nums[pointer], nums[high]] = [nums[high], nums[pointer]];
          return pointer;
      }
      

      Explanation:

      1. Initial Array: [3, 2, 1, 5, 6, 4]
      2. k = 2: We need to find the 2nd largest element.

      Step 1: Partition the array

      • Pivot element = 4
      • Array after partitioning: [3, 2, 1, 4, 6, 5]
      • Pivot index = 3

      Step 2: Recursive Selection

      • Target index = 4 (since we need the 2nd largest element, which is the 4th index in 0-based indexing)
      • Pivot index (3) < Target index (4): Search in the right partition [6, 5]

      Step 3: Partition the right partition

      • Pivot element = 5
      • Array after partitioning: [3, 2, 1, 4, 5, 6]
      • Pivot index = 4

      Final Step: Return the element at the target index

      • Element at index 4: 5

      Time Complexity:

      • Average Case: The average time complexity of Quickselect is O(n).
      • Worst Case: The worst-case time complexity is O(n^2), but this is rare with good pivot selection.

      Space Complexity:

      • In-Place: The space complexity is O(1) because the algorithm works in place.

      위 내용은 배열에서 K번째로 큰 요소의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.