Comment le faire fonctionner dans O (n)?

Possible en double:
Interview Q: given an array of numbers, return array of products of all other numbers (no division)Comment le faire fonctionner dans O (n)?

je suis tombé sur une tâche/question d'entrevue qui m'a vraiment fait réfléchir ... alors voilà:

Vous avez un tableau A [N] de N nombres. Vous devez composer une sortie de tableau [N] telle que la sortie [i] sera égale à la multiplication de tous les éléments de A [N] sauf A [i]. Par exemple, la sortie [0] sera la multiplication de A [1] à A [N-1] et la sortie [1] sera la multiplication de A [0] et de A [2] à A [N-1]. Résolvez-le sans opérateur de division et dans O (n).

J'ai vraiment essayé de trouver une solution mais je me retrouve toujours avec une complexité de O (n^2). Peut-être est-ce quelqu'un de plus intelligent que moi qui peut me dire un algorithme qui fonctionne en O (n) ou au moins me donner un indice ...

Source

2010-05-26 evermean

Je refuse de répondre à ce genre de questions d'entrevue, franchement. C'était juste correct jusqu'à ce que je lis "sans opérateur de division". –

@daniel: ils n'excluaient pas pow (n, -1) 'et cette question méritait amplement une réponse en l'utilisant ... – msw

@KennyTM, n'est-ce pas une compagnie avec une offre d'emploi sur Stack Overflow qui utilise cette question d'entrevue? :-) –

Construire deux tableaux temporaires - B [N] et C [N]. Former chaque élément de B [N] comme le produit des éléments A [N] à sa gauche (y compris elle-même) - en travaillant de gauche à droite, N opérations. Former chaque élément de C [N] comme le produit des éléments A [N] à sa droite (y compris elle-même) - en procédant de droite à gauche, N opérations. Puis A [n] = B [n-1] * C [n + 1] - un autre N opérations à travailler sur ce. Vous vous retrouvez avec un peu moins de 3N opérations, qui est O (N). C'est juste court, parce que B [0] et C [N-1], et le premier et le dernier A, ne nécessitent pas de multiplication. Aussi, C [0] = B [N-1], donc je pense que vous devriez avoir besoin exactement des opérations 3N-5.

Source

2010-05-26 07:54:31

Quelle est la logique derrière cette idée? Je l'ai mis en place et ça fonctionne bien, mais toute logique derrière? – Barry

Barry, prenez la séquence "1 2 3 4" par exemple, dessinez la matrice 4x4 et remplissez ces valeurs dans chaque rangée avec la diagonale centrale laissant vide. Vous verrez la logique derrière cette idée. – Dalius

Vous générez deux tableaux intermédiaires, L, où L[i] = products of A[0]..A[i-1] et U où U[i] = products of A[i+1]..A[N-1]. Ceux-ci peuvent tous deux être générés dans O (n). Votre valeur de sortie B[i] sera juste L[i] * U[i] - encore une fois c'est O (n).

Source

2010-05-26 07:58:41

Tricher Je sais, mais: -

for (x = 0 ; x < n ; x++) { 
    bigtot = bigtot * in[x]; 
} 
for (x = 0 ; x < n ; x++) { 
     out[n] = bigot; 
     for (y = in[x]; y > 0 ; y--) { 
     out[n] = out[n] - in[x] 
     } 
}

Source

2010-05-26 07:59:49

Cela ne me ressemble pas O (N)? –

Pas vraiment la deuxième boucle dépend de la valeur individuelle d'une entrée de table particulière - donc c'est mauvais pour chaque entrée, mais ajouter une autre entrée affecte juste la nouvelle entrée donc c'est O (N) même si chaque n est assez horrible –

Comment le faire fonctionner dans O (n)?

Répondre

Questions connexes