Kième plus grand élément d'un tableau

#️⃣ Tableau, file d'attente prioritaire, sélection rapide

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

? Comprendre le problème

Si le tableau est [8, 6, 12, 9, 3, 4] et que k vaut 2, vous devez trouver le 2ème plus grand élément de ce tableau. Tout d'abord, vous trierez le tableau : [3, 4, 6, 8, 9, 12] La sortie sera 9 car il s'agit du deuxième plus grand élément.

✅ Force brute

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

Explication:

1. Tri du tableau : Le tableau est trié par ordre croissant à l'aide de la méthode de tri.
2. Trouver le kème élément le plus grand : Le kème élément le plus grand est trouvé en accédant à l'élément à l'index nums.length - k.

Complexité temporelle :

• Tri : La complexité temporelle du tri d'un tableau est (O(nlog n)), où (n) est la longueur du tableau.
• Accès à l'élément : Accéder à un élément dans un tableau est O(1).

Donc, la complexité temporelle globale est O(n log n).

Complexité spatiale :

• Tri sur place : La méthode de tri trie le tableau sur place, donc la complexité spatiale est O(1) pour l'opération de tri.
• Global : Puisque nous n'utilisons aucune structure de données supplémentaire, la complexité globale de l'espace est O(1).

✅ Mieux

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

Explication:

1. Tableau initial : [2, 1, 6, 3, 5, 4]
2. k = 3 : Il faut trouver le 3ème plus grand élément.

Étape 1 : Ajouter les k premiers éléments au min-heap

• Tas après avoir ajouté 2 : [2]
• Tas après avoir ajouté 1 : [1, 2]
• Tas après avoir ajouté 6 : [1, 2, 6]

Étape 2 : Parcourir les éléments restants

• Élément actuel = 3

  • Tas avant comparaison : [1, 2, 6]
  • Plus petit élément du tas (minHeap.front().element) : 1
  • Comparaison : 3> 1
  • Action : Supprimez 1 et ajoutez 3
  • Tas après mise à jour : [2, 6, 3]

  • Élément actuel = 5

    • Tas avant comparaison : [2, 6, 3]
    • Plus petit élément du tas (minHeap.front().element) : 2
    • Comparaison : 5> 2
    • Action : Supprimez 2 et ajoutez 5
    • Tas après mise à jour : [3, 6, 5]

  • Élément actuel = 4

    • Tas avant comparaison : [3, 6, 5]
    • Plus petit élément du tas (minHeap.front().element) : 3
    • Comparaison : 4> 3
    • Action : Supprimez 3 et ajoutez 4
    • Tas après mise à jour : [4, 6, 5]

  Dernière étape : renvoyer la racine du tas

  • Tas : [4, 6, 5]
  • 3ème plus grand élément : 4 (la racine du tas)

  Complexité temporelle :

  • Opérations sur le tas : l'insertion et la suppression d'éléments du tas prennent un temps O(log k).
  • Global : Puisque nous effectuons ces opérations pour chacun des n éléments du tableau, la complexité temporelle globale est O(n log k).

  Complexité spatiale :

  • Stockage en tas : La complexité spatiale est O(k) car le tas stocke au plus k éléments.

  ✅ Meilleur

  Remarque : même si Leetcode restreint la sélection rapide, vous devez vous souvenir de cette approche car elle réussit la plupart des cas de test
  

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

  Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!