配列内の K 番目に大きい要素

#️⃣ 配列、優先キュー、クイック選択

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

?問題を理解する

配列が [8, 6, 12, 9, 3, 4] で、k が 2 の場合、この配列内で 2 番目に大きい要素を見つける必要があります。まず、配列を並べ替えます: [3, 4, 6, 8, 9, 12] 2 番目に大きい要素であるため、出力は 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. 配列の並べ替え: 配列は、sort メソッドを使用して昇順で並べ替えられます。
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: 3 番目に大きい要素を見つける必要があります。

ステップ 1: 最初の k 要素を最小ヒープに追加する

• 2 追加後のヒープ: [2]
• 1追加後のヒープ: [1, 2]
• 6を追加した後のヒープ: [1, 2, 6]

ステップ 2: 残りの要素を反復処理する

• 現在の要素 = 3

  • 比較前のヒープ: [1, 2, 6]
  • ヒープ内の最小要素 (minHeap.front().element): 1
  • 比較: 3 > 1
  • アクション: 1 を削除し、3 を追加します
  • 更新後のヒープ: [2, 6, 3]

• 現在の要素 = 5

  • 比較前のヒープ: [2, 6, 3]
  • ヒープ内の最小要素 (minHeap.front().element): 2
  • 比較: 5 > 2
  • アクション: 2 を削除して 5 を追加します
  • 更新後のヒープ: [3, 6, 5]

• 現在の要素 = 4

  • 比較前のヒープ: [3, 6, 5]
  • ヒープ内の最小要素 (minHeap.front().element): 3
  • 比較: 4 > 3
  • アクション: 3 を削除し、4 を追加します
  • 更新後のヒープ: [4, 6, 5]

最後のステップ: ヒープのルートを返す

• ヒープ: [4, 6, 5]
• 3 番目に大きい要素: 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 中国語 Web サイトの他の関連記事を参照してください。