. Trouver la K-ème plus petite distance de paire

719. Trouver la K-ème plus petite distance de paire

Difficulté : Difficile

Sujets : Tableau, deux pointeurs, recherche binaire, tri

La distance d'une paire d'entiers a et b est définie comme la différence absolue entre a et b.

Étant donné un tableau entier nums et un entier k, renvoie la k^ième la plus petite distance parmi toutes les paires nums[i] et nums[j] où 0 < ;= je ≪ j &Lt ; nums.length.

Exemple 1 :

• Entrée : nums = [1,3,1], k = 1
• Sortie : 0
• Explication : Voici toutes les paires :

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2




Alors la 1ère la plus petite paire de distances est (1,1), et sa distance est 0.

Exemple 2 :



Entrée : nums = [1,1,1], k = 2

Sortie : 0


Exemple 3 :



Entrée : nums = [1,6,1], k = 3

Sortie : 5


Contraintes :


n == nums.length
2 <= n <= 104

0 <= nums[i] <= 106

1 <= k <= n * (n - 1) / 2


Indice :


Recherche binaire de la réponse. Comment pouvez-vous vérifier combien de paires ont une distance <= X ?


Solution :

Nous pouvons utiliser une combinaison de recherche binaire et de technique à deux pointeurs. Voici une approche étape par étape pour résoudre ce problème :


  
  
  Approche:



Trier le tableau : Tout d'abord, triez les numéros du tableau. Le tri permet de calculer efficacement le nombre de paires avec une distance inférieure ou égale à une valeur donnée.
Recherche binaire sur la distance : utilisez la recherche binaire pour trouver la k-ème plus petite distance. L'espace de recherche des distances va de 0 (la plus petite distance possible) à max(nums) - min(nums) (la plus grande distance possible).
Compter les paires avec une distance ≤ Mid : Pour chaque valeur médiane dans la recherche binaire, comptez le nombre de paires avec une distance inférieure ou égale au milieu. Cela peut être fait efficacement en utilisant une approche à deux points.
Ajuster la plage de recherche binaire : En fonction du nombre de paires avec une distance inférieure ou égale au milieu, ajustez la plage de recherche binaire. Si le nombre est inférieur à k, augmentez la limite inférieure ; sinon, diminuez la limite supérieure.


Implémentons cette solution en PHP : 719. Trouver la K-ième plus petite distance de paire


  
  
  Explication:



countPairsWithDistanceLessThanOrEqualTo : Cette fonction compte combien de paires ont une distance inférieure ou égale au milieu. Il utilise deux pointeurs, où right est l'élément actuel et left est ajusté jusqu'à ce que la différence entre nums[right] et nums[left] soit inférieure ou égale à mid.
smallestDistancePair : Cette fonction utilise la recherche binaire pour trouver la k-ème plus petite distance. Les valeurs basse et haute définissent la plage de recherche actuelle pour les distances. La valeur moyenne est vérifiée à l'aide de la fonction countPairsWithDistanceLessThanOrEqualTo. En fonction du résultat, l'espace de recherche est ajusté.


Cet algorithme trouve efficacement la k-ème plus petite distance de paire avec une complexité temporelle de O(n log(max(nums) - min(nums)) + n log n).

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
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!