[LeetCode]238. Idées pour résoudre le produit de tableaux autres que lui-même.

Titre

Vous donne un tableau d'entiers nums de longueur n, où n > 1, renvoie la sortie du tableau de sortie, où output[i] est égal à tous les autres éléments en nums sauf le produit nums[i] de .

Exemple :

Entrée : [1,2,3,4]
Sortie : [24,12,8,6]

Conseils : Les données de la question garantissent que le produit de tous les éléments de préfixe et suffixes (même le tableau entier) de tout élément du tableau est compris dans la plage d'entiers de 32 bits.

Instructions : Veuillez ne pas utiliser de division et répondez à cette question dans un délai de complexité de temps O(n).

Avancé : Pouvez-vous résoudre ce problème dans un espace de complexité constante ? (Aux fins de l'analyse de la complexité spatiale, le tableau de sortie n'est pas considéré comme un espace supplémentaire.).

Solution

La première pensée après avoir répondu à la question est : deux pour les boucles, une pour le produit et une pour la division. Mais plus tard, j’ai découvert que les instructions indiquaient de ne pas utiliser la division, j’ai donc dû utiliser d’autres méthodes.

Puisque nous calculons la multiplication cumulative sauf pour nous-mêmes, nous pouvons utiliser la position actuelle comme point de division pour calculer respectivement le produit des éléments de gauche et le produit des éléments de droite, puis multipliez-les.

Ceci a la solution suivante :

Algorithme 1 (extrait de la solution officielle LeetCode) :

Initialiser deux tableaux vides L et R. Pour un indice donné i, L[i] représente le produit de tous les nombres à gauche de i, et R[i] représente le produit de tous les nombres à droite de i.

Nous devons utiliser deux boucles pour remplir les valeurs des tableaux L et R. Pour le tableau L, L[0] doit être 1 car il n'y a aucun élément à gauche du premier élément. Pour les autres éléments : L[i] = L[i-1] * nums[i-1].

De même, pour le tableau R, R[length-1] devrait être 1. la longueur fait référence à la taille du tableau d’entrée. Autres éléments : R[i] = R[i+1] * nums[i+1].

Lorsque les tableaux R et L sont remplis, il suffit de parcourir le tableau d'entrée, et la valeur à l'index i est : L[i] * R[i].

class Solution {
    public int[] productExceptSelf(int[] nums) {
  int arrLen = nums.length;
  int[] leftNums = new int[arrLen];
  int[] rightNums = new int[arrLen];
  leftNums[0] = 1;rightNums[arrLen-1] = 1;
  
  for(int i = 1; i < arrLen; i++){
   leftNums[i] = leftNums[i-1] * nums[i-1];
   rightNums[arrLen-i-1] = rightNums[arrLen-i] * nums[arrLen-i];
  }
  
  for(int i = 0; i < arrLen; i++){
   leftNums[i] *= rightNums[i];
  }
  
  return leftNums;
 }
}

Analyse de complexité

Complexité temporelle : O(N), où N fait référence à la taille du tableau nums. Le prétraitement des tableaux L et R et le calcul final du parcours sont tous deux des complexités temporelles O (N).

Complexité spatiale : O(N), où N fait référence à la taille des numéros du tableau. Les tableaux L et R sont utilisés pour construire la réponse. La longueur des tableaux L et R est la taille des numéros du tableau.

Algorithme 2 : Méthode de tableau partagé

L'idée générale est la même que l'idée officielle de résolution de problèmes : Multiplication à gauche * multiplication à droite.

Définissez le tableau de retour returnNums et considérez-le comme un tableau partagé, tout en remplissant les données des extrémités gauche et droite, puis définissez left et right pour stocker la gauche ; et les bons produits et l'itération de la boucle sont renouvelés.

1. Avant que les deux pointeurs ne se rencontrent, remplissez simplement le tableau

2. Lorsque les deux interagissent (uniquement lorsque la longueur est impaire), sa valeur de remplissage ; est gauche*droite.

3. Après la rencontre des deux, la valeur du tableau doit être remplie avec la valeur finale : car la partie gauche a déjà stocké le produit gauche, et le produit droit est sur le point d'être calculé ; la partie droite a stocké le bon produit, nous sommes sur le point d’obtenir le produit gauche. Alors multipliez-les directement. returnNums[i] = gauche et returnNums[j] = droite.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int arrLen = nums.length;
        int[] returnNums = new int[arrLen];
        int left = 1, right = 1;    // 临时存储
        returnNums[0] = 1; returnNums[arrLen-1] = 1;
        for(int i = 1, j = arrLen-2; i < arrLen; i++, j--){
            left *= nums[i-1];
            right *= nums[j+1];
            if(i < j){  // 两指针为交会
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 两指针重合，奇数位情况下发生
                returnNums[i] = left*right;
            }else{              // 两指针错位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

Analyse de complexité

Complexité temporelle : O(N), de la même manière que le problème précédent, une boucle de longueur N est réalisée, et sa complexité temporelle est O(N).

Complexité spatiale : O(1), comme mentionné dans le titre, l'espace du tableau renvoyé n'est pas compté, donc l'espace de stockage supplémentaire utilisé est laissé et c'est vrai. Par conséquent, il n’existe qu’un niveau de complexité spatiale constant.

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!