Kth Elemen Terbesar dalam Tatasusunan

#️⃣ Tatasusunan, Barisan Keutamaan, Pilih Pantas

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

? Fahami Masalah

Jika tatasusunan ialah [8, 6, 12, 9, 3, 4] dan k ialah 2, anda perlu mencari elemen ke-2 terbesar dalam tatasusunan ini. Pertama, anda akan mengisih tatasusunan: [3, 4, 6, 8, 9, 12] Outputnya ialah 9 kerana ia adalah elemen kedua terbesar.

✅ Bruteforce

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];
};

Penjelasan:

1. Isih Tatasusunan: Tatasusunan diisih mengikut tertib menaik menggunakan kaedah isihan.
2. Mencari Elemen Terbesar ke-k: Elemen terbesar ke-k ditemui dengan mengakses elemen di nombor indeks.length - k.

Kerumitan Masa:

• Isih: Kerumitan masa mengisih tatasusunan ialah (O(nlog n)), dengan (n) ialah panjang tatasusunan.
• Mengakses Elemen: Mengakses elemen dalam tatasusunan ialah O(1).

Jadi, kerumitan masa keseluruhan ialah O(n log n).

Kerumitan Ruang:

• Isih Di Tempat: Kaedah isihan mengisih tatasusunan di tempatnya, jadi kerumitan ruang ialah O(1) untuk operasi isihan.
• Keseluruhan: Memandangkan kami tidak menggunakan sebarang struktur data tambahan, kerumitan ruang keseluruhan ialah O(1).

✅ Lebih baik

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;
    };

Penjelasan:

1. Tatasusunan Awal: [2, 1, 6, 3, 5, 4]
2. k = 3: Kita perlu mencari elemen ke-3 terbesar.

Langkah 1: Tambahkan elemen k pertama pada timbunan min

• Timbunan selepas menambah 2: [2]
• Timbunan selepas menambah 1: [1, 2]
• Timbunan selepas menambah 6: [1, 2, 6]

Langkah 2: Lelaran melalui elemen yang tinggal

• Elemen semasa = 3

  • Timbunan sebelum perbandingan: [1, 2, 6]
  • Elemen terkecil dalam timbunan (minHeap.front().elemen): 1
  • Perbandingan: 3 > 1
  • Tindakan: Alih keluar 1 dan tambah 3
  • Timbunan selepas kemas kini: [2, 6, 3]

  • Elemen semasa = 5

    • Timbunan sebelum perbandingan: [2, 6, 3]
    • Elemen terkecil dalam timbunan (minHeap.front().elemen): 2
    • Perbandingan: 5 > 2
    • Tindakan: Alih keluar 2 dan tambah 5
    • Timbunan selepas kemas kini: [3, 6, 5]

  • Elemen semasa = 4

    • Timbunan sebelum perbandingan: [3, 6, 5]
    • Elemen terkecil dalam timbunan (minHeap.front().elemen): 3
    • Perbandingan: 4 > 3
    • Tindakan: Alih keluar 3 dan tambah 4
    • Timbunan selepas kemas kini: [4, 6, 5]

  Langkah Akhir: Kembalikan akar timbunan

  • Timbunan: [4, 6, 5]
  • elemen ke-3 terbesar: 4 (akar timbunan)

  Kerumitan Masa:

  • Kendalian Timbunan: Memasukkan dan mengalih keluar elemen daripada timbunan mengambil masa O(log k).
  • Keseluruhan: Memandangkan kami melaksanakan operasi ini untuk setiap elemen n dalam tatasusunan, kerumitan masa keseluruhan ialah O(n log k).

  Kerumitan Ruang:

  • Storan Timbunan: Kerumitan ruang ialah O(k) kerana timbunan menyimpan paling banyak unsur k.

  ✅ Terbaik

  Nota: Walaupun Leetcode mengehadkan pemilihan pantas, anda harus ingat pendekatan ini kerana ia melepasi kebanyakan kes ujian
  

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

  Atas ialah kandungan terperinci Kth Elemen Terbesar dalam Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!