Séquence carrée la plus longue dans un tableau

2501. La plus longue séquence carrée dans un tableau

Difficulté :Moyen

Sujets : Tableau, table de hachage, recherche binaire, programmation dynamique, tri

Vous recevez un tableau de nombres entiers. Une sous-séquence de nombres est appelée une séquence carrée si :

• La longueur de la sous-séquence est d'au moins 2, et
• après tri de la sous-séquence, chaque élément (sauf le premier élément) est le carré du numéro précédent.

Renvoie la longueur de la séquence carrée la plus longue en chiffres, ou renvoie -1 s'il n'y a pas de séquence carrée.

Une sous-séquence est un tableau qui peut être dérivé d'un autre tableau en supprimant certains ou aucun élément sans changer l'ordre des éléments restants.

Exemple 1 :

• Entrée : nums = [4,3,6,16,8,2]
• Sortie : 3
• Explication : Choisissez la sous-séquence [4,16,2]. Après l'avoir trié, cela devient [2,4,16].
  • 4 = 2*2.
  • 16 = 4*4.
  • Par conséquent, [4,16,2] est une séquence carrée.
  • On peut montrer que toute sous-séquence de longueur 4 n'est pas une séquence carrée.

Exemple 2 :

• Entrée : nums = [2,3,5,6,7]
• Sortie : -1
• Explication : Il n'y a pas de séquence carrée dans les chiffres donc retournez -1.

Contraintes :

• 2 <= nums.length <= 10⁵
• 2 <= nums[i] <= 10⁵

Indice :

1. Avec les contraintes, la longueur de la plus longue séquence carrée possible est de 5.
2. Stockez les éléments de nums dans un ensemble pour vérifier rapidement s'il existe.

Solution :

Nous devons identifier la séquence carrée la plus longue dans le tableau nums. Une séquence carrée est une sous-séquence où chaque élément suivant est le carré de l'élément précédent et doit comporter au moins deux éléments de long.

Voici l'approche de la solution :

1. Utiliser un ensemble pour une recherche rapide :

   • Stockez les nombres dans un ensemble pour vérifier rapidement si le carré d'un élément est également dans le tableau.

2. Parcourir le tableau :

   • Pour chaque nombre du tableau, essayez de construire une séquence carrée à partir de ce nombre.
   • Vérifiez si le carré du numéro actuel existe dans l'ensemble et continuez à prolonger la séquence jusqu'à ce qu'il n'y ait plus de correspondance de carré.

3. Longueur maximale de la piste :

   • Suivez la longueur maximale de toutes les stries carrées possibles rencontrées. Si aucune séquence carrée n'est trouvée, renvoie -1.

4. Optimisation :

   • Triez le tableau avant de vérifier chaque élément pour vous assurer que la sous-séquence est vérifiée par ordre croissant. Cela permettra d'éviter les contrôles redondants.

Implémentons cette solution en PHP : 2501. Séquence carrée la plus longue dans un tableau

  
  
  Explication:




Tri : le tri des nombres garantit que nous pouvons vérifier les séquences par ordre croissant.

Set Lookup : l'utilisation de array_flip crée une structure de type ensemble pour $numSet avec $nums comme clés, permettant des vérifications d'existence rapides.

Parcourez chaque nombre : Pour chaque nombre en nombres, vérifiez si le carré du nombre actuel est dans l'ensemble. Si c’est le cas, continuez la séquence. Sinon, interrompez la séquence et vérifiez si c’est la plus longue trouvée.



  
  
  Analyse de complexité




Complexité temporelle : O(n log n) due au tri, où n est le nombre d'éléments en chiffres. Les recherches ultérieures et les vérifications de séquences carrées sont O(n).

Complexité spatiale : O(n), principalement pour stocker des nombres dans l'ensemble.


Cette solution trouve efficacement la séquence carrée la plus longue ou renvoie -1 si aucune séquence valide n'existe.

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!