Trouver le tableau commun de préfixe de deux tableaux

2657. Trouver le tableau commun de préfixe de deux tableaux

Difficulté :Moyen

Sujets : Tableau, table de hachage, manipulation de bits

Vous recevez deux indexés 0 permutations entières A et B de longueur n.

Un tableau commun de préfixes de A et B est un tableau C tel que C[i] est égal au nombre de nombres présents à ou avant l'index i dans A et B.

Renvoyer le tableau commun de préfixes de A et B.

Une séquence de n entiers est appelée une permutation si elle contient tous les entiers de 1 à n exactement une fois.

Exemple 1 :

• Entrée : A = [1,3,2,4], B = [3,1,2,4]
• Sortie : [0,2,3,4]
• Explication : À i = 0 : aucun nombre n'est commun, donc C[0] = 0.
  • À i = 1 : 1 et 3 sont communs dans A et B, donc C[1] = 2.
  • À i = 2 : 1, 2 et 3 sont communs dans A et B, donc C[2] = 3.
  • À i = 3 : 1, 2, 3 et 4 sont communs dans A et B, donc C[3] = 4.

Exemple 2 :

• Entrée : A = [2,3,1], B = [3,1,2]
• Sortie : [0,1,3]
• Explication : À i = 0 : aucun nombre n'est commun, donc C[0] = 0.
  • À i = 1 : seul 3 est commun dans A et B, donc C[1] = 1.
  • À i = 2 : 1, 2 et 3 sont communs dans A et B, donc C[2] = 3.

Contraintes :

• 1 <= A.longueur == B.longueur == n <= 50
• 1 <= A[i], B[i] <= n
• Il est garanti que A et B sont tous deux une permutation de n entiers.

Indice :

1. Envisagez de conserver un tableau de fréquences qui stocke le nombre d'occurrences de chaque nombre jusqu'à l'index i.
2. Si un nombre est apparu deux fois, cela signifie qu'il s'est produit à la fois dans A et dans B puisqu'il s'agit tous deux de permutations, alors ajoutez-en un à la réponse.

Solution :

Nous pouvons parcourir les deux tableaux A et B tout en gardant une trace des nombres qui se sont produits au niveau ou avant l'index actuel dans les deux tableaux. Étant donné que les deux tableaux sont des permutations du même ensemble de nombres, nous pouvons utiliser deux jeux de hachage (ou tableaux) pour stocker les nombres qui sont apparus au niveau ou avant l'index actuel dans les deux tableaux. Pour chaque index, nous pouvons compter les nombres communs qui sont apparus dans les deux tableaux jusqu'à ce point.

Approche de la solution :

1. Utilisez deux tableaux pour suivre les occurrences de nombres dans A et B jusqu'à l'index i.
2. Pour chaque index i, vérifiez si A[i] et B[i] ont déjà été vus. Si tel est le cas, incrémentez le nombre commun.
3. Utilisez un tableau de fréquences pour suivre la présence de nombres de 1 à n dans les deux tableaux.

Implémentons cette solution en PHP : 2657. Trouver le tableau commun de préfixe de deux tableaux

<?php
/**
 * @param Integer[] $A
 * @param Integer[] $B
 * @return Integer[]
 */
function findThePrefixCommonArray($A, $B) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]

$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<strong>Tableaux de fréquences</strong> : Nous maintenons deux tableaux de fréquences, freqA et freqB, où chaque index représente un nombre dans la permutation.

<ul>
<li>Lorsque nous rencontrons un nombre dans A[i] ou B[i], nous augmentons la valeur correspondante dans le tableau de fréquences.</li>
</ul>
</li>
<li>
<strong>Common Count</strong> : Après avoir mis à jour les tableaux de fréquences pour A[i] et B[i], nous vérifions pour chaque numéro s'il est apparu dans les deux tableaux jusqu'à l'index i. Si tel est le cas, nous augmentons le commonCount.</li>
<li>
<strong>Résultat</strong> : Le décompte commun est stocké dans le tableau de résultats pour chaque index.</li>
</ol>

<h3>
  
  
  Exemple de procédure pas à pas :
</h3>

<p>Pour la saisie :<br>
</p>

<pre class="brush:php;toolbar:false">$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];

• À i = 0 : Pas encore de nombres communs → C[0] = 0
• À i = 1 : Les nombres 1 et 3 sont communs → C[1] = 2
• À i = 2 : les nombres 1, 2 et 3 sont communs → C[2] = 3
• À i = 3 : les nombres 1, 2, 3 et 4 sont communs → C[3] = 4

Sortie : [0, 2, 3, 4]

Complexité temporelle :

• O(n²⁾ : Pour chaque index i, nous vérifions chaque élément de 1 à n pour voir s'il est commun, ce qui rend cette solution quadratique en complexité temporelle. Ceci est acceptable compte tenu de la contrainte n ≤ 50.

Cela devrait fonctionner efficacement dans les limites données.

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!