Sous-tableau le plus court avec OR au moins K II

3097. Sous-tableau le plus court avec OU au moins K II

Difficulté :Moyen

Sujets : Tableau, manipulation de bits, fenêtre coulissante

Vous recevez un tableau numérique d'entiers non négatifs et un entier k.

Un tableau est dit spécial si le OU au niveau du bit de tous ses éléments est au moins k.

Renvoie la longueur du sous-tableau spécial non vide le plus court¹ de nombres, ou renvoie -1 s'il n'existe aucun sous-tableau spécial.

Exemple 1 :

• Entrée : nums = [1,2,3], k = 2
• Sortie : 1
• Explication : Le sous-tableau [3] a une valeur OR de 3. Par conséquent, nous renvoyons 1.

Exemple 2 :

• Entrée : nums = [2,1,8], k = 10
• Sortie : 3
• Explication : Le sous-tableau [2,1,8] a une valeur OR de 11. Par conséquent, nous renvoyons 3.

Exemple 3 :

• Entrée : nums = [1,2], k = 0
• Sortie : 1
• Explication : Le sous-tableau [1] a une valeur OR de 1. Par conséquent, nous renvoyons 1.

Contraintes :

• 1 <= nums.length <= 2 * 10⁵
• 0 <= nums[i] <= 10⁹
• 0 <= k <= 10⁹

Indice :

1. Pour chaque nums[i], nous pouvons conserver le résultat OU au niveau du bit de chaque sous-tableau se terminant par lui.
2. La propriété du OU au niveau du bit est qu'il ne désactive aucun bit et ne définit que de nouveaux bits
3. Donc, le nombre de résultats différents pour chaque nums[i] est au plus égal au nombre de bits 32.

Solution :

Nous pouvons utiliser une approche de fenêtre glissante combinée à une manipulation de bits pour garder une trace du OU des éléments dans la fenêtre.

Plan:

1. Approche par fenêtre coulissante : parcourez le tableau à l'aide de deux pointeurs, en conservant un sous-tableau dont la valeur OR est vérifiée.
2. OU au niveau du bit : l'opération OU accumule des valeurs. Cela ne réduit jamais le résultat (c'est-à-dire qu'une fois qu'un bit est mis à 1, il ne peut pas être désactivé). Cela signifie que lorsque nous étendons la fenêtre, la valeur OR ne fait qu'augmenter ou rester la même.
3. Efficacité : Nous pouvons utiliser un deque (file d'attente à double extrémité) pour maintenir les indices des sous-tableaux. Cela nous permet de faire glisser efficacement la fenêtre tout en gardant une trace de la longueur minimale du sous-réseau.

Mesures:

1. Parcourez le tableau, pour chaque élément, maintenez un OU en cours d'exécution.
2. Pour chaque élément, vérifiez si le OU est supérieur ou égal à k. Si c'est le cas, essayez de réduire la fenêtre du côté gauche.
3. La fenêtre coulissante doit être déplacée efficacement en gardant une trace de la valeur OU dans une structure deque pour permettre un glissement et un rétrécissement en temps constant.

Implémentons cette solution en PHP : 3097. Sous-tableau le plus court avec OU au moins K II

minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1

$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3

$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>





  
  
  Explication:




Méthode minimumSubarrayLength :


Initialiser et à une valeur élevée impossible ($n 1).
Utilisez deux pointeurs l (gauche) et r (droite) pour agrandir et réduire la fenêtre.
Calculez le OU du sous-tableau lorsque vous agrandissez la fenêtre avec orNum et réduisez-la avec undoOrNum lors de la réduction.
Chaque fois que le résultat OR atteint ou dépasse k, vérifiez si la taille actuelle de la fenêtre est inférieure à ans.



Méthodes orNum et undoOrNum :



Méthode orNum : ajoute des bits au OU cumulatif en mettant à jour le tableau de comptage. Si un bit est nouvellement défini dans la fenêtre (ce qui signifie que count[i] devient 1), ce bit est ajouté à ors.

Méthode undoOrNum : supprime les bits du OU cumulatif lorsque vous faites glisser la fenêtre vers la gauche. Si un bit n'est plus défini dans aucun des nombres de la fenêtre (ce qui signifie que count[i] devient 0), ce bit est supprimé de ors.



Complexité temporelle :


La complexité temporelle est O(n) car chaque index est ajouté et supprimé du deque au plus une fois.

n est la longueur du tableau d'entrée.




4*Complexité temporelle* :


La complexité spatiale est O(n) pour stocker le tableau préfixe OR et le deque.


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








Sous-tableau : Un sous-tableau est une séquence contiguë non vide 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!