Comptez le nombre de paires équitables

2563. Comptez le nombre de paires équitables

Difficulté :Moyen

Sujets : Tableau, deux pointeurs, recherche binaire, tri

Étant donné un tableau d'entiers indexé à 0 de taille n et deux entiers inférieur et supérieur, renvoie le nombre de paires équitables.

Une paire (i, j) est juste si :

• 0 ≪= je ≪ j &Lt ; n, et
• inférieur <= nums[i] nums[j] <= supérieur

Exemple 1 :

• Entrée : nums = [0,1,7,4,4,5], inférieur = 3, supérieur = 6
• Sortie : 6
• Explication : Il existe 6 paires équitables : (0,3), (0,4), (0,5), (1,3), (1,4) et (1,5) .

Exemple 2 :

• Entrée : nums = [1,7,9,2,5], inférieur = 11, supérieur = 11
• Sortie : 1
• Explication : Il existe une seule paire juste : (2,3).

Contraintes :

• 1 <= nums.length <= 10⁵
• nums.length == n
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= inférieur <= supérieur <= 10⁹

Indice :

1. Trier le tableau par ordre croissant.
2. Pour chaque nombre du tableau, gardez une trace des nombres les plus petits et les plus grands du tableau qui peuvent former une paire équitable avec ce nombre.
3. À mesure que vous passez à un nombre plus grand, les deux limites diminuent.

Solution :

Nous pouvons utiliser l'approche suivante :

1. Trier le tableau : le tri nous aide à exploiter la technique à deux pointeurs et à effectuer des recherches binaires plus efficacement.
2. Technique à deux pointeurs : Pour chaque élément du tableau trié, nous pouvons calculer la plage d'éléments qui peuvent former une paire équitable avec lui. Nous utilisons la recherche binaire pour trouver cette plage.
3. Recherche binaire de limites : pour chaque élément nums[i], recherchez la plage [inférieure, supérieure] - nums[i] pour j > je. Nous utilisons la recherche binaire pour trouver les indices les plus petits et les plus grands qui satisfont à cette plage.

Implémentons cette solution en PHP : 2563. Comptez le nombre de paires équitables


<?php
/**
* @param Integer[] $nums
* @param Integer $lower
* @param Integer $upper
* @return Integer
*/
function countFairPairs($nums, $lower, $upper) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
* Helper function for binary search to find left boundary
*
* @param $arr
* @param $target
* @param $start
* @return int|mixed
*/
function lowerBound($arr, $target, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
* Helper function for binary search to find right boundary
*
* @param $arr
* @param $target
* @param $start
* @return int|mixed
*/
function upperBound($arr, $target, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [0, 1, 7, 4, 4, 5];
$lower = 3;
$upper = 6;
echo countFairPairs($nums, $lower, $upper);  // Output: 6
?>

Explication:

1. Tri : Nous trions les numéros du tableau pour faciliter la recherche de paires valides avec la recherche binaire.
2. Limites de recherche binaire :
   • Pour chaque élément nums[i], nous trouvons les valeurs basse et haute, qui sont les limites dans lesquelles nous voulons que la somme tombe.
   • Nous utilisons deux recherches binaires pour trouver la plage d'indices [gauche, droite) où nums[i] nums[j] se situe dans [inférieur, supérieur].
3. Comptage des paires : Nous ajoutons le nombre d'indices valides entre gauche et droite pour chaque i.

Cette approche a une complexité temporelle de O(n log n) en raison du tri et de la recherche binaire pour chaque élément, ce qui est suffisamment efficace pour les entrées volumineuses.

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!