K-tes größtes Element in einem Array

#️⃣ Array, Prioritätswarteschlange, Schnellauswahl

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

? Problem verstehen

Wenn das Array [8, 6, 12, 9, 3, 4] ist und k 2 ist, müssen Sie das zweitgrößte Element in diesem Array finden. Zuerst sortieren Sie das Array: [3, 4, 6, 8, 9, 12] Die Ausgabe ist 9, da es das zweitgrößte Element ist.

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

Erläuterung:

1. Sortieren des Arrays: Das Array wird mithilfe der Sortiermethode in aufsteigender Reihenfolge sortiert.
2. Das k-größte Element finden: Das k-größte Element wird gefunden, indem auf das Element am Index nums.length - k zugegriffen wird.

Zeitkomplexität:

• Sortierung: Die zeitliche Komplexität der Sortierung eines Arrays beträgt (O(nlog n)), wobei (n) die Länge des Arrays ist.
• Zugriff auf das Element: Der Zugriff auf ein Element in einem Array ist O(1).

Die Gesamtzeitkomplexität beträgt also O(n log n).

Raumkomplexität:

• In-Place-Sortierung: Die Sortiermethode sortiert das Array an Ort und Stelle, sodass die Platzkomplexität für den Sortiervorgang O(1) ist.
• Insgesamt: Da wir keine zusätzlichen Datenstrukturen verwenden, beträgt die Gesamtkomplexität des Raums O(1).

✅ Besser

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

Erläuterung:

1. Anfängliches Array: [2, 1, 6, 3, 5, 4]
2. k = 3: Wir müssen das drittgrößte Element finden.

Schritt 1: Fügen Sie die ersten k Elemente zum Min-Heap hinzu

• Heap nach dem Hinzufügen von 2: [2]
• Heap nach dem Hinzufügen von 1: [1, 2]
• Heap nach dem Hinzufügen von 6: [1, 2, 6]

Schritt 2: Durchlaufen Sie die verbleibenden Elemente

• Aktuelles Element = 3

  • Haufen vor Vergleich: [1, 2, 6]
  • Kleinstes Element im Heap (minHeap.front().element): 1
  • Vergleich: 3 > 1
  • Aktion: 1 entfernen und 3 hinzufügen
  • Heap nach Update: [2, 6, 3]

  • Aktuelles Element = 5

    • Haufen vor Vergleich: [2, 6, 3]
    • Kleinstes Element im Heap (minHeap.front().element): 2
    • Vergleich: 5 > 2
    • Aktion: 2 entfernen und 5 hinzufügen
    • Heap nach Update: [3, 6, 5]

  • Aktuelles Element = 4

    • Haufen vor Vergleich: [3, 6, 5]
    • Kleinstes Element im Heap (minHeap.front().element): 3
    • Vergleich: 4 > 3
    • Aktion: 3 entfernen und 4 hinzufügen
    • Heap nach Update: [4, 6, 5]

  Letzter Schritt: Geben Sie die Wurzel des Heaps zurück

  • Haufen: [4, 6, 5]
  • Drittgrößtes Element: 4 (die Wurzel des Heaps)

  Zeitkomplexität:

  • Heap-Operationen: Das Einfügen und Entfernen von Elementen aus dem Heap dauert O(log k) Zeit.
  • Insgesamt: Da wir diese Operationen für jedes der n Elemente im Array ausführen, beträgt die Gesamtzeitkomplexität O(n log k).

  Raumkomplexität:

  • Heap-Speicher: Die Raumkomplexität beträgt O(k), da der Heap höchstens k Elemente speichert.

  ✅ Am besten

  Hinweis: Auch wenn Leetcode die Schnellauswahl einschränkt, sollten Sie sich an diesen Ansatz erinnern, da er die meisten Testfälle besteht
  

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

  Das obige ist der detaillierte Inhalt vonK-tes größtes Element in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!