Product of Array Except Self

Q: Por que a divisão não é permitida em Product of Array Except Self?

Dividir o produto total por nums[i] não funciona quando o array contém um zero, porque o total é 0 e o índice do próprio zero exigiria uma divisão por 0. Para fazer isso funcionar, é preciso contar os zeros e tratar casos especiais. Essa regra leva você aos produtos de prefixo e sufixo, que lidam com zeros sem nenhum caso especial.

MédioSoma de prefixos

+10

Você recebe um array de números inteiros nums. Retorne um array answer do mesmo tamanho, em que answer[i] é o produto de todos os elementos de nums, exceto o que está no índice i. Faça isso em tempo O(n) e sem usar divisão.

Função

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: o array de números inteiros, com pelo menos dois elementos
Retornainteger-array: um array cujo valor no índice i é o produto de todos os elementos, exceto nums[i]

Restrições

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
O produto de todos os valores diferentes de zero em nums cabe em um inteiro com sinal de 32 bits, então todo produto calculado ao longo do caminho também cabe.

Exemplos

Entrada: nums = [2, 3, 4, 5]
Saída: [60, 40, 30, 24]
Explicação: Deixando o 2 de fora, temos 3 × 4 × 5 = 60, e deixando o 5 de fora, temos 2 × 3 × 4 = 24. Os dois do meio funcionam da mesma forma: 2 × 4 × 5 = 40 e 2 × 3 × 5 = 30.

+14 testes ocultos ao enviar

Para ir além

Você consegue usar apenas espaço extra O(1), sem contar o array que você retorna?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

O produto de tudo, exceto nums[i], é o produto dos valores à esquerda multiplicado pelo produto dos valores à direita. Dividir o produto total por nums[i] parece mais curto, mas isso não é permitido aqui e falha quando há zeros, pois o produto total é 0. Os produtos de prefixo e sufixo fornecem todos os produtos à esquerda e à direita em duas passagens, então a resposta leva O(n) de tempo. O array de saída pode armazenar os produtos à esquerda, e uma variável guarda o produto à direita, portanto não é necessário nenhum outro array.

Multiplique os outros para cada índice

Correta, mas não termina nos maiores testes

Intuição

Siga a definição. Para cada índice i, comece um produto em 1 e multiplique cada nums[j] cujo índice j não seja i. Ignorar esse índice, em vez de dividi-lo depois, mantém os zeros inofensivos: em [-2, 5, 0, 3], o produto para o índice 2 nunca inclui o 0 e resulta em -30.

Está correto, mas repete trabalho. Os produtos para o índice 0 e o índice 1 compartilham todos os valores, exceto dois, e você acaba multiplicando todos eles novamente. Cada uma das n posições exige n-1 multiplicações, cerca de 10^8 no total quando n = 10^4. C consegue fazer isso em uma fração de segundo, mas Python, Ruby ou R demoram demais.

Algoritmo

Crie um array de respostas com tamanho n.
Para cada índice i, defina product como 1.
Multiplique product por cada nums[j] cujo índice j não seja i.
Armazene product no índice i do array de respostas.
Retorne o array de respostas.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Arrays de produtos de prefixos e sufixos

Intuição

Divida o produto do índice i em dois: os valores antes de i e os valores depois dele. Chame esses produtos de before[i] e after[i]. Então answer[i] = before[i] × after[i], e nums[i] fica de fora, sem nenhuma divisão.

cada array cresce a partir do vizinho com uma multiplicação. before[0] é 1, o produto de nenhum valor, e before[i] = before[i-1] × nums[i-1]. Do outro lado, after[n-1] é 1 e after[i] = after[i+1] × nums[i+1]. Para [2, 3, 4, 5], você obtém before = [1, 2, 6, 24] e after = [60, 20, 5, 1]; multiplicando-os posição por posição, o resultado é [60, 40, 30, 24].

Três passagens de n etapas levam tempo O(n). Os dois arrays auxiliares custam O(n) de memória extra, que a próxima abordagem elimina.

Algoritmo

Preencha before da esquerda para a direita: before[0] = 1, depois cada elemento é o elemento anterior multiplicado pelo valor anterior.
Preencha after da direita para a esquerda: after[n-1] = 1, depois cada elemento é o próximo elemento multiplicado pelo próximo valor.
Defina answer[i] como before[i] × after[i] para cada índice.
Retorne answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Produtos à esquerda na resposta, um produto à direita em execução

Intuição

Você nunca precisa do array after inteiro de uma só vez. Percorrendo a partir da extremidade direita, o produto dos valores à direita de i é um único número. Mantenha-o em uma variável right e atualize-o com uma multiplicação por etapa.

Então, escreva os produtos à esquerda diretamente no array de resposta em uma primeira passagem. Em uma segunda passagem, da direita para a esquerda, multiplique answer[i] por right e só então multiplique right por nums[i]. A ordem importa: quando você usa right no índice i, ele ainda não deve incluir nums[i].

Para [2, 3, 4, 5], a primeira passagem deixa [1, 2, 6, 24]. A segunda passagem usa right = 1, 5, 20, 60 nos índices 3, 2, 1, 0 e transforma o array em [60, 40, 30, 24]. O tempo continua sendo O(n) e, além do array retornado, a memória extra é uma variável: O(1).

Algoritmo

Defina answer[0] = 1 e, em seguida, da esquerda para a direita, defina answer[i] = answer[i-1] × nums[i-1].
Defina right como 1.
Do último índice até 0, multiplique answer[i] por right.
Em seguida, multiplique right por nums[i].
Retorne answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Armadilhas e casos extremos

Os bugs aqui vêm dos zeros, da ordem das duas atualizações na segunda passagem e das extremidades do array.

Dividir o produto total por nums[i] falha quando aparece um 0. Para [-2, 5, 0, 3], o total é 0, e o índice 2 precisaria calcular 0 dividido por 0. Contar os zeros pode contornar isso, mas o problema proíbe divisão de qualquer forma.
Multiplicar right por nums[i] antes de usá-lo inclui nums[i] no próprio produto. Para [2, 3, 4, 5], o último valor passa a ser 120 em vez de 24.
Iniciar os produtos à esquerda com nums[0] em vez de 1. Não há nada à esquerda do índice 0, então o produto à esquerda é o produto vazio, 1, e answer[0] acaba sendo apenas o produto dos valores à sua direita.
Limites dos loops: a passagem da esquerda lê nums[i-1], então começa no índice 1. Um array de sufixos lê nums[i+1], então começa em n-2.
Dois zeros fazem com que todas as respostas sejam 0. Um zero faz com que todas as respostas sejam 0, exceto a do próprio índice do zero. Teste os dois casos antes de confiar no seu código.

Perguntas frequentes4

Qual é a complexidade de tempo de Product of Array Except Self?

A solução com prefixos e sufixos é executada em tempo O(n): uma passagem da esquerda para a direita e outra da direita para a esquerda. Com os produtos à esquerda armazenados no array de saída e um único produto acumulado à direita, ela precisa de O(1) de espaço extra, além do espaço de saída. Multiplicar todos os outros valores para cada índice leva O(n²) de tempo.

Por que a divisão não é permitida em Product of Array Except Self?

Dividir o produto total por nums[i] não funciona quando o array contém um zero, porque o total é 0 e o índice do próprio zero exigiria uma divisão por 0. Para fazer isso funcionar, é preciso contar os zeros e tratar casos especiais. Essa regra leva você aos produtos de prefixo e sufixo, que lidam com zeros sem nenhum caso especial.

A matriz de saída conta como espaço extra?

Não. Você precisa retornar a resposta de qualquer forma, então a convenção usual não a inclui na contagem de espaço. Portanto, armazenar nele os produtos da esquerda e manter o produto da direita em uma variável conta como espaço extra O(1).

Como Product of Array Except Self lida com zeros?

Com os produtos de prefixo e sufixo, os zeros não precisam de um caso especial. Qualquer produto à esquerda ou à direita que passe por um zero é 0, e o produto do próprio índice do zero o ignora. Com dois ou mais zeros, todos os produtos contêm um, então todas as respostas são 0.

Python

def productExceptSelf(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 3, 4, 5]

Esperado

[60, 40, 30, 24]

Product of Array Except Self

Função

Restrições

Exemplos

Dicas

Solução

Multiplique os outros para cada índice

Arrays de produtos de prefixos e sufixos

Produtos à esquerda na resposta, um produto à direita em execução

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos