Tableau spécial II

3152. Tableau spécial II

Difficulté :Moyen

Sujets : Tableau, recherche binaire, somme de préfixes

Un tableau est considéré comme spécial si chaque paire de ses éléments adjacents contient deux nombres de parité différente.

Vous recevez un tableau de nombres entiers et une matrice de requêtes entières 2D, où pour les requêtes[i] = [from_i, to_i] votre tâche est de vérifier que sous-tableau¹ nums[from_i..to_i] est spécial ou non.

Renvoyer un tableau de réponses booléennes telles que la réponse[i] est vraie si nums[from_i..to_i] est spécial.

Exemple 1 :

• Entrée : nums = [3,4,1,2,6], requêtes = [[0,4]]
• Sortie : [faux]
• Explication : Le sous-tableau est [3,4,1,2,6]. 2 et 6 sont tous les deux pairs.

Exemple 2 :

• Entrée : nums = [4,3,1,6], requêtes = [[0,2],[2,3]]
• Sortie : [faux, vrai]
• Explication :

1. Le sous-tableau est [4,3,1]. 3 et 1 sont tous deux impairs. La réponse à cette question est donc fausse.
2. Le sous-tableau est [1,6]. Il n'y a qu'une seule paire : (1,6) et elle contient des nombres de parité différente. La réponse à cette question est donc vraie.

Contraintes :

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵
• 1 <= requêtes.length <= 10⁵
• requêtes[i].length == 2
• 0 <= requêtes[i][0] <= requêtes[i][1] <= nums.length - 1

Indice :

1. Essayez de diviser le tableau en sous-tableaux spéciaux continus non intersectés.
2. Pour chaque requête, vérifiez que le premier et le dernier élément de cette requête sont dans le même sous-tableau ou non.

Solution :

Nous devons déterminer si un sous-tableau de nombres est « spécial », c'est-à-dire que chaque paire d'éléments adjacents dans le sous-tableau doit avoir une parité différente (l'un doit être impair et l'autre doit être pair).

Approche:

1. Identifier les transitions paritaires : Nous pouvons prétraiter le tableau pour marquer les positions où la parité change. Par exemple:
   • 0 représente un nombre pair.
   • 1 représente un nombre impair.

L'idée est d'identifier toutes les positions où les éléments adjacents ont des parités différentes. Cela nous aidera à déterminer efficacement si un sous-tableau est spécial en vérifiant si les positions dans la requête font partie du même bloc "spécial".

1. Prétraitement :
   Créez un tableau binaire parity_change où chaque élément vaut 1 si les éléments adjacents ont une parité différente, sinon 0. Par exemple :

   • Si nums[i] et nums[i 1] ont une parité différente, définissez parity_change[i] = 1, sinon 0.

2. Tableau de somme de préfixes :
   Construisez un tableau de somme de préfixes prefix_sum où chaque entrée à l'index i représente le nombre cumulé de transitions de parité jusqu'à cet index. Cela permet de vérifier rapidement si toutes les paires d'un sous-tableau ont une parité différente.

3. Traitement des requêtes :
   Pour chaque requête [de, à], vérifiez s'il existe une position dans la plage [de, à-1] où la parité ne change pas. Cela peut être fait en vérifiant la différence entre les valeurs de la somme des préfixes : prefix_sum[to] - prefix_sum[from].

Implémentons cette solution en PHP : 3152. Tableau spécial II

<?php
/**
 * @param Integer[] $nums
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function specialArray($nums, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [3,4,1,2,6];
$queries1 = [[0, 4]];
print_r(specialArray($nums1, $queries1)); // [false]

$nums2 = [4,3,1,6];
$queries2 = [[0, 2], [2, 3]];
print_r(specialArray($nums2, $queries2)); // [false, true]
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li><p><strong>Prétraitement des transitions de parité :</strong><br>
On calcule parity_change[i] = 1 si les éléments nums[i] et nums[i 1] ont des parités différentes. Sinon, nous le mettons à 0.</p></li>
<li><p><strong>Tableau de somme de préfixes :</strong><br>
Le prefix_sum[i] stocke le nombre cumulé de transitions de parité depuis le début du tableau jusqu'à l'index i. Cela nous permet de calculer combien de transitions se sont produites dans n'importe quel sous-tableau [de, à] en temps constant en utilisant la formule :<br>
</p></li>
</ol>

<pre class="brush:php;toolbar:false">   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. Évaluation des requêtes : Pour chaque requête, si le nombre de transitions est égal à la longueur du sous-tableau moins 1, le sous-tableau est spécial et nous renvoyons vrai. Sinon, nous renvoyons faux.

Complexité temporelle :

• Le prétraitement des transitions de parité prend O(n).
• La construction du tableau de somme de préfixes prend O(n).
• Chaque requête peut recevoir une réponse en O(1) en utilisant le tableau de somme de préfixes.
• Par conséquent, la complexité temporelle totale est O(n q), où n est la longueur du tableau et q est le nombre de requêtes.

Cette solution gère efficacement les contraintes du problème avec une approche optimisée.

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

1. Sous-tableau Un sous-tableau est une séquence contiguë d'éléments au sein d'un tableau. ↩

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!