. 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

Ladistance d'une paired'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, renvoiela k^ièmela plus petitedistance parmi toutes les pairesnums[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èrela 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 auréférentielsur 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!