Première rangée ou colonne entièrement peinte

2661. Première ligne ou colonne entièrement peinte

Difficulté :Moyen

Sujets : Tableau, table de hachage, matrice

Vous recevez un tableau d'entiers indexé à 0 et un tapis matrice entier m x n. arr et mat contiennent tous deux tous les entiers compris dans la plage [1, m * n].

Parcourez chaque index i dans arr à partir de l'index 0 et peignez la cellule en mat contenant l'entier arr[i].

Renvoyer le plus petit indice i auquel une ligne ou une colonne sera entièrement peinte en mat.

Exemple 1 :

• Entrée : arr = [1,3,4,2], mat = [[1,4],[2,3]]
• Sortie : 2
• Explication : Les mouvements sont affichés dans l'ordre, et la première ligne et la deuxième colonne de la matrice deviennent entièrement peintes à arr[2].

Exemple 2 :

• Entrée : arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[ 8,7,9]]
• Sortie : 3
• Explication : La deuxième colonne devient entièrement peinte à l'arr[3].

Contraintes :

• m == mat.longueur
• n = mat[i].longueur
• arr.length == m * n
• 1 5
• 1 5
• 1
• Tous les entiers de arr sont uniques.
• Tous les entiers de mat sont uniques.

Indice :

1. Pouvons-nous utiliser un réseau de fréquences ?
2. Prétraitez les positions des valeurs dans la matrice.
3. Parcourez le tableau et incrémentez la fréquence de ligne et de colonne correspondante en utilisant les positions prétraitées.
4. Si la fréquence des lignes devient égale au nombre de colonnes, ou vice versa, renvoie l'index actuel.

Solution :

Nous pouvons suivre ces étapes :

Approche

1. Prétraiter les positions des éléments :

   • Tout d'abord, nous devons stocker les positions des éléments dans la matrice. Nous pouvons créer un dictionnaire (position_map) qui mappe chaque valeur de la matrice à sa position (ligne, col).

2. Tableaux de fréquences :

   • Nous avons besoin de deux tableaux de fréquences : un pour les lignes et un pour les colonnes.
   • Au fur et à mesure que nous parcourons le tableau arr, nous incrémenterons la fréquence de la ligne et de la colonne respectives pour chaque élément.

3. Vérifier la ligne ou la colonne complète :

   • Après chaque incrément, vérifiez si une ligne ou une colonne devient complètement peinte (c'est-à-dire que sa fréquence atteint la taille des colonnes ou des lignes de la matrice).
   • Si c'est le cas, renvoie l'index actuel.

4. Renvoyer le résultat :

   • L'index où une ligne ou une colonne est entièrement peinte est notre réponse.

Étapes détaillées

1. Créez une carte position_map pour chaque valeur dans mat jusqu'à sa position (ligne, col).
2. Créez des tableaux row_count et col_count pour suivre le nombre de cellules peintes dans chaque ligne et colonne.
3. Parcourez l'arr et pour chaque élément, mettez à jour le nombre de lignes et de colonnes respectives.
4. Si à un moment donné une ligne ou une colonne est complètement peinte, renvoyez cet index.

Implémentons cette solution en PHP : 2661. Première rangée ou colonne entièrement peinte

<?php /**
 * @param Integer[] $arr
 * @param Integer[][] $mat
 * @return Integer
 */
function firstCompleteIndex($arr, $mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr = [1, 3, 4, 2];
$mat = [[1, 4], [2, 3]];
echo firstCompleteIndex($arr, $mat); // Output: 2

$arr = [2, 8, 7, 4, 1, 3, 5, 6, 9];
$mat = [[3, 2, 5], [1, 4, 6], [8, 7, 9]];
echo firstCompleteIndex($arr, $mat); // Output: 3
?>

Explication:

1. Postes de pré-traitement :

   • Nous construisons un dictionnaire position_map où chaque valeur de mat est mappée à sa position (ligne, col). Cela permet d'accéder directement à la position de n'importe quelle valeur en temps constant pendant le parcours de l'arr.

2. Compte de fréquence :

   • Nous initialisons les tableaux row_count et col_count avec des zéros. Ces tableaux garderont une trace du nombre de fois qu'une cellule d'une ligne ou d'une colonne spécifique a été peinte.

3. Parcours du tableau :

   • Pour chaque valeur dans arr, nous recherchons sa position dans position_map, puis incrémentons le nombre de lignes et de colonnes correspondant.
   • Après avoir mis à jour les décomptes, nous vérifions si une ligne ou une colonne a atteint sa taille maximale (c'est-à-dire row_count[$row] == n ou col_count[$col] == m). Si tel est le cas, nous renvoyons l'index actuel i.

4. Résultat du retour :

   • Le premier index où une ligne ou une colonne est entièrement peinte est renvoyé.

Complexité temporelle :

• Pré-traitement : Nous construisons position_map en O(m * n).
• Traversal : Nous traitons chaque élément de arr (qui a une longueur de m * n), et pour chaque élément, nous effectuons des opérations à temps constant pour mettre à jour et vérifier les fréquences de ligne et de colonne, ce qui prend O( 1) le temps.
• Dans l'ensemble, la complexité temporelle est O(m * n).

Complexité spatiale :

• Nous stockons les positions de tous les éléments dans position_map et nous utilisons l'espace O(mn) pour les tableaux de fréquences. Par conséquent, la complexité spatiale est O(m * n).

Cette solution devrait gérer efficacement le problème dans les limites des contraintes 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!