719. Trouver la K-iè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 d'entiers nums et un entier k, renvoie la k^ème la plus petite distance parmi toutes les paires nums[i] et nums[j] où 0 .

Exemple 1 :

• Entrée : nombres = [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 plus petite paire de distances est (1,1), et sa distance est 0.

Exemple 2 :

• Entrée : nombres = [1,1,1], k = 2
• Sortie : 0

Exemple 3 :

• Entrée : nombres = [1,6,1], k = 3
• Sortie : 5

Contraintes :

• n == nums.longueur
• 2 4
• 0 6
• 1

Indice:

1. Recherche binaire de la réponse. Comment pouvez-vous vérifier combien de paires ont une distance

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:

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

2. 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).

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

4. 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 le nombre de paires ayant 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