A pergunta fácil da entrevista ficou mais difícil: dados os números 1..100, encontre o (s) número (s) ausente (s), dado exatamente k estão ausentes

1146

Eu tive uma experiência interessante de entrevista de emprego há um tempo. A pergunta começou muito fácil:

Q1 : Temos um saco contendo números 1, 2, 3, ..., 100. Cada número aparece exatamente uma vez, então existem 100 números. Agora, um número é escolhido aleatoriamente da sacola. Encontre o número que falta.

Já ouvi essa pergunta da entrevista antes, é claro, então respondi muito rapidamente ao longo das linhas de:

A1 : Bem, a soma dos números 1 + 2 + 3 + … + Né (N+1)(N/2)(veja Wikipedia: soma das séries aritméticas ). Pois N = 100a soma é 5050.

Assim, se todos os números estiverem presentes na sacola, a soma será exatamente 5050. Como falta um número, a soma será menor que isso e a diferença é esse número. Para que possamos encontrar esse número ausente no O(N)tempo e no O(1)espaço.

Nesse ponto, pensei ter me saído bem, mas, de repente, a pergunta deu uma guinada inesperada:

P2 : Isso está correto, mas agora como você faria isso se dois números estiverem faltando?

Eu nunca tinha visto / ouvido / considerado essa variação antes, então entrei em pânico e não consegui responder à pergunta. O entrevistador insistiu em conhecer meu processo de pensamento, então mencionei que talvez possamos obter mais informações comparando com o produto esperado, ou talvez fazendo uma segunda passagem depois de coletar algumas informações da primeira passagem, etc., mas eu realmente estava apenas filmando no escuro, em vez de realmente ter um caminho claro para a solução.

O entrevistador tentou me encorajar dizendo que ter uma segunda equação é realmente uma maneira de resolver o problema. Nesse ponto, fiquei meio chateado (por não saber a resposta antes) e perguntei se essa é uma técnica de programação geral (leia-se: "útil"), ou se é apenas uma resposta de truque / pegadinha.

A resposta do entrevistador me surpreendeu: você pode generalizar a técnica para encontrar três números ausentes. De fato, você pode generalizá-lo para encontrar k números ausentes.

Qk : Se exatamente faltam k números da sacola, como você os encontrará com eficiência?

Isso foi há alguns meses atrás e eu ainda não conseguia descobrir o que é essa técnica. Obviamente há um Ω(N)tempo limite inferior, uma vez que deve verificar todos os números, pelo menos uma vez, mas o entrevistador insistiu que o TEMPO e ESPAÇO complexidade da técnica de resolução (menos a O(N)varredura de entrada tempo) é definida em k não N .

Portanto, a pergunta aqui é simples:

  • Como você resolveria o Q2 ?
  • Como você resolveria o terceiro trimestre ?
  • Como você resolveria o Qk ?

Esclarecimentos

  • Geralmente existem N números de 1 .. N , não apenas 1..100.
  • Não estou procurando a solução óbvia baseada em conjunto, por exemplo, usando um conjunto de bits , codificando a presença / ausência de cada número pelo valor de um bit designado, usando O(N)bits em espaço adicional. Não podemos permitir qualquer proporcional de espaço adicional para N .
  • Também não estou procurando a abordagem óbvia do tipo primeiro. Vale a pena mencionar isso e a abordagem baseada em conjuntos em uma entrevista (eles são fáceis de implementar e, dependendo de N , podem ser muito práticos). Estou procurando a solução do Santo Graal (que pode ou não ser prática de implementar, mas tem as características assintóticas desejadas).

Então, novamente, é claro que você deve escanear a entrada O(N), mas você pode capturar apenas uma pequena quantidade de informação (definida em termos de k e não N ) e, em seguida, deve encontrar os k números ausentes de alguma forma.

poligenelubricants
fonte
7
@polygenelubricants Obrigado pelos esclarecimentos. "Estou procurando um algoritmo que use o tempo O (N) e o espaço O (K) em que K é a contagem de números ausentes" estaria claro desde o início ;-)
Dave O.
7
Você deve precisar, na declaração do primeiro trimestre, que não pode acessar os números em ordem. Isso provavelmente parece óbvio para você, mas nunca ouvi falar da pergunta e o termo "bolsa" (que também significa "várias configurações") era meio confuso.
Jérémie
7
Por favor, leia o seguinte, pois as respostas fornecidas aqui são ridículas: stackoverflow.com/questions/4406110/…
18
A solução de somar os números requer espaço de log (N), a menos que você considere o requisito de espaço para um número inteiro ilimitado como O (1). Mas se você permitir números inteiros ilimitados, terá o espaço que desejar com apenas um número inteiro.
Udo Klein
3
A propósito, uma solução alternativa bastante agradável para o primeiro trimestre poderia ser computar XORtodos os números de 1até e n, em seguida, obter resultados com todos os números na matriz fornecida. No final, você tem o seu número ausente. Nesta solução, você não precisa se preocupar com o estouro, como na síntese.
Sbeliakov 23/09/2015

Respostas:

590

Aqui está um resumo do link de Dimitris Andreou .

Lembre-se da soma dos i-ésimos poderes, onde i = 1,2, .., k. Isso reduz o problema para resolver o sistema de equações

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Usando as identidades de Newton , saber b i permite calcular

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Se você expandir o polinômio (xa 1 ) ... (xa k ), os coeficientes serão exatamente c 1 , ..., c k - veja as fórmulas de Viète . Como todos os fatores polinomiais são únicos (o anel de polinômios é um domínio euclidiano ), isso significa que i são determinados exclusivamente, até a permutação.

Isso termina uma prova de que lembrar poderes é suficiente para recuperar os números. Para constante k, essa é uma boa abordagem.

No entanto, quando k está variando, a abordagem direta da computação c 1 , ..., c k é proibitivamente cara, pois, por exemplo, c k é o produto de todos os números ausentes, magnitude n! / (Nk) !. Para superar isso, faça cálculos no campo Z q , onde q é um primo tal que n <= q <2n - existe pelo postulado de Bertrand . A prova não precisa ser alterada, pois as fórmulas ainda se mantêm e a fatoração de polinômios ainda é única. Você também precisa de um algoritmo para fatorar sobre campos finitos, por exemplo, o de Berlekamp ou Cantor-Zassenhaus .

Pseudocódigo de alto nível para constante k:

  • Calcular a i-ésima potência de determinados números
  • Subtraia para obter somas de i-ésimas potências de números desconhecidos. Chame as somas b i .
  • Use as identidades de Newton para calcular coeficientes de b i ; chame-os de c i . Basicamente, c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 ) / 2; veja Wikipedia para fórmulas exatas
  • Fatore o polinômio x k -c 1 x k-1 + ... + c k .
  • As raízes do polinômio são os números necessários a 1 , ..., a k .

Para variar k, encontre um primo n <= q <2n usando, por exemplo, Miller-Rabin, e execute as etapas com todos os números de módulo reduzido q.

EDIT: A versão anterior desta resposta afirmou que, em vez de Z q , onde q é primo, é possível usar um campo finito da característica 2 (q = 2 ^ (log n)). Não é esse o caso, uma vez que as fórmulas de Newton requerem divisão por números até k.

sdcvvc
fonte
6
Você não precisa usar um campo primário, também pode usar q = 2^(log n). (Como você fez as super e subscritos ?!)
Heinrich Apfelmus
49
+1 Isso é muito, muito inteligente. Ao mesmo tempo, é questionável se vale realmente a pena o esforço ou se (partes desta) solução para um problema bastante artificial pode ser reutilizada de outra maneira. E mesmo que este fosse um problema do mundo real, em muitas plataformas a O(N^2)solução mais trivial provavelmente superará essa beleza por até razoavelmente alta N. Me faz pensar nisso: tinyurl.com/c8fwgw No entanto, um ótimo trabalho! Eu não teria tido a paciência para rastreamento através de toda a matemática :)
back2dos
167
Eu acho que essa é uma resposta maravilhosa. Eu acho que isso também ilustra o quão ruim seria uma questão de entrevista para estender os números ausentes para além de um. Até o primeiro é meio que um gotchya, mas é bastante comum que basicamente mostre "você fez alguma preparação para entrevistas". Mas esperar que um especialista em CS saiba ir além de k = 1 (especialmente "in loco" em uma entrevista) é um pouco tolo.
corsiKa
5
Isso está efetivamente fazendo a codificação Reed Solomon na entrada.
precisa
78
Aposto que inserir todos os números em um hash sete fazer iterações no 1...Nconjunto usando pesquisas para determinar se os números estão faltando seria o mais genérico, o mais rápido em média em relação às kvariações, a solução mais debugável, mais sustentável e compreensível. É claro que o caminho da matemática é impressionante, mas em algum ponto do caminho você precisa ser um engenheiro e não um matemático. Especialmente quando os negócios estão envolvidos.
precisa saber é o seguinte
243

Você o encontrará lendo as duas páginas de Muthukrishnan - Algoritmos de fluxo de dados: Enigma 1: Encontrando números ausentes . Mostra exatamente a generalização que você está procurando . Provavelmente é isso que o entrevistador leu e por que ele fez essas perguntas.

Agora, se apenas as pessoas começassem a excluir as respostas que foram substituídas ou substituídas pelo tratamento de Muthukrishnan, e tornassem esse texto mais fácil de encontrar. :)


Veja também a resposta diretamente relacionada ao sdcvvc , que também inclui o pseudocódigo (viva! Não é necessário ler essas formulações matemáticas complicadas :)) (obrigado, ótimo trabalho!).

Dimitris Andreou
fonte
Oooh ... Isso é interessante. Eu tenho que admitir que fiquei um pouco confuso com a matemática, mas eu estava apenas analisando. Pode deixá-lo aberto para ver mais tarde. :) E +1 para obter este link mais acessível. ;-) #
Chris
2
O link do google books não funciona para mim. Aqui está uma versão melhor [PostScript File].
Heinrich Apfelmus
9
Uau. Eu não esperava que isso fosse votado! Na última vez em que publiquei uma referência à solução (da Knuth, nesse caso), em vez de tentar resolvê-la, ela foi realmente diminuída: stackoverflow.com/questions/3060104/… O bibliotecário dentro de mim se alegra, obrigado :)
Dimitris Andreou
@ Apfelmus, observe que este é um rascunho. (Não culpo você, é claro, confundi o rascunho com as coisas reais por quase um ano antes de encontrar o livro). Se o link não funcionou, você pode acessar books.google.com e pesquisar "Algoritmos de fluxo de dados Muthukrishnan" (sem aspas), é o primeiro a aparecer.
Dimitris Andreou
2
Por favor, leia o seguinte, pois as respostas fornecidas aqui são ridículas: stackoverflow.com/questions/4406110/…
174

Podemos resolver o Q2 somando os números em si e os quadrados dos números.

Podemos então reduzir o problema para

k1 + k2 = x
k1^2 + k2^2 = y

Onde xe onde yestão as somas abaixo dos valores esperados.

Substituir nos dá:

(x-k2)^2 + k2^2 = y

Que podemos resolver para determinar nossos números ausentes.

Anon.
fonte
7
+1; Eu tentei a fórmula no Maple para selecionar números e funciona. Eu ainda não conseguia me convencer POR QUE funciona, no entanto.
polygenelubricants
4
@polygenelubricants: Se você quiser provar a exatidão, primeiro mostrará que ela sempre fornece uma solução correta (ou seja, sempre produz um par de números que, ao removê-los do conjunto, resultaria no restante do conjunto soma observada e soma dos quadrados). A partir daí, provar a exclusividade é tão simples quanto mostrar que ele produz apenas um par de números.
Anon.
5
A natureza das equações significa que você obterá dois valores de k2 dessa equação. No entanto, a partir da primeira equação que você usa para gerar k1, você pode ver que esses dois valores de k2 significarão que k1 é o outro valor, portanto, você tem duas soluções com os mesmos números ao contrário. Se você declarou abitrariamente que k1> k2, teria apenas uma solução para a equação quadrática e, portanto, uma solução geral. E, claramente, pela natureza da pergunta, uma resposta sempre existe e sempre funciona.
Chris
3
Para uma determinada soma k1 + k2, existem muitos pares. Podemos escrever esses pares como K1 = a + be K2 = ab onde a = (K1 + k2 / 2). a é único para uma determinada soma. A soma dos quadrados (a + b) ** 2 + (ab) ** 2 = 2 * (a 2 + b 2). Para uma dada soma K1 + K2, o termo a 2 é fixo e vemos que a soma dos quadrados será única devido ao termo b 2. Portanto, os valores x e y são exclusivos para um par de números inteiros.
phkahler
8
Isso é incrível. @ user3281743 aqui está um exemplo. Deixe os números ausentes (k1 e k2) serem 4 e 6. Soma (1 -> 10) = 55 e Soma (1 ^ 2 -> 10 ^ 2) = 385. Agora, deixe x = 55 - (Soma (todos os números restantes )) e y = 385 - (Soma (quadrados de todos os números restantes)), portanto, x = 10 e y = 52. Substitua como mostrado, o que nos deixa com: (10 - k2) ^ 2 + k2 ^ 2 = 52 que você pode simplifique para: 2k ^ 2 - 20k + 48 = 0. A resolução da equação quadrática fornece 4 e 6 como resposta.
AlexKoren
137

Como @j_random_hacker apontou, isso é bastante semelhante a Encontrar duplicatas no tempo O (n) e no espaço O (1) , e uma adaptação da minha resposta aqui também funciona aqui.

Supondo que a "bolsa" seja representada por uma matriz A[]de tamanho baseada em 1 N - k, podemos resolver Qk no O(N)tempo e no O(k)espaço adicional.

Primeiro, estendemos nossa matriz A[]por kelementos, para que ela agora tenha tamanho N. Este é o O(k)espaço adicional. Em seguida, executamos o seguinte algoritmo de pseudo-código:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

O primeiro loop inicializa as kentradas extras da mesma forma que a primeira entrada na matriz (este é apenas um valor conveniente que sabemos que já está presente na matriz - após esta etapa, todas as entradas que estavam faltando na matriz inicial de tamanho N-ksão ainda falta na matriz estendida).

O segundo loop permite a matriz estendida, de modo que, se o elemento xestiver presente pelo menos uma vez, uma dessas entradas estará na posição A[x].

Observe que, embora tenha um loop aninhado, ele ainda é executado no O(N)tempo - uma troca ocorre apenas se houver uma ital que A[i] != i, e cada troca define pelo menos um elemento como aquele A[i] == i, onde isso não era verdade antes. Isso significa que o número total de swaps (e, portanto, o número total de execuções do whilecorpo do loop) é no máximo N-1.

O terceiro loop imprime os índices da matriz ique não são ocupados pelo valor i- isso significa que ideve estar faltando.

caf
fonte
4
Eu me pergunto por que tão poucas pessoas votam nessa resposta e nem a marcaram como uma resposta correta. Aqui está o código em Python. É executado em O (n) tempo e precisa de espaço extra O (k). pastebin.com/9jZqnTzV
wall-e
3
@ caf isso é bem parecido com definir os bits e contar os lugares onde o bit é 0. E eu acho que enquanto você cria uma matriz inteira, mais memória é ocupada.
22413 Fox
5
"Definir os bits e contar os locais em que o bit é 0" requer O (n) espaço extra, esta solução mostra como usar O (k) espaço extra.
Caf 12/12
7
Não funciona com fluxos como entrada e modifica a matriz de entrada (embora eu goste muito e a ideia seja proveitosa).
Comco
3
@ v.oddou: Não, está tudo bem. A troca será alterada A[i], o que significa que a próxima iteração não comparará os mesmos dois valores que o anterior. O novo A[i]será o mesmo do último loop A[A[i]], mas o novo A[A[i]]será um novo valor. Experimente e veja.
caf
128

Pedi a uma criança de 4 anos para resolver este problema. Ele ordenou os números e depois contou. Isso requer um espaço necessário de O (piso da cozinha) e funciona tão facilmente quanto muitas bolas faltam.

Coronel Panic
fonte
20
;) seu filho de 4 anos deve estar se aproximando de 5 ou / e é um gênio. minha filha de 4 anos ainda não pode contar adequadamente até 4. para ser justo, digamos que ela mal finalmente integrou a existência do "4". caso contrário, até agora, ela sempre a ignorava. "1,2,3,5,6,7" era sua sequência de contagem usual. Pedi-lhe para adicionar lápis e ela conseguiria 1 + 2 = 3 desnumerando tudo novamente do zero. Estou preocupado, na verdade ...: '(me ..
v.oddou 03/04
abordagem simples, mas eficaz.
PabTorre
6
O (chão da cozinha) haha ​​- mas não seria O (n ^ 2)?
13
O (m²), eu acho :) :)
Viktor Mellgren
1
@ phuclv: a resposta afirmou que "Isso requer espaço de O (piso da cozinha)". Mas, em qualquer caso, este é um exemplo em que a classificação pode ser alcançada em O (n) tempo --- veja esta discussão .
Anthony Labarre
36

Não tenho certeza, se é a solução mais eficiente, mas eu repetiria todas as entradas e usaria um conjunto de bits para lembrar quais números estão definidos e, em seguida, testaria 0 bits.

Gosto de soluções simples - e até acredito que pode ser mais rápido que calcular a soma, a soma dos quadrados etc.

Chris Lercher
fonte
11
Eu propus essa resposta óbvia, mas não era isso que o entrevistador queria. Eu disse explicitamente na pergunta que essa não é a resposta que estou procurando. Outra resposta óbvia: classifique primeiro. Nem o O(N)tipo de contagem nem o tipo de O(N log N)comparação é o que estou procurando, embora sejam soluções muito simples.
polygenelubricants
@polygenelubricants: Não consigo encontrar onde você disse isso na sua pergunta. Se você considerar o resultado do conjunto de bits, não haverá segunda passagem. A complexidade é (se considerarmos N constante, como sugere o entrevistador, que a complexidade é "definida em k e não N") O (1), e se você precisar construir um resultado mais "limpo", você obtenha O (k), que é o melhor que você pode obter, porque você sempre precisa de O (k) para criar o resultado limpo.
Chris Lercher
"Observe que não estou procurando a solução óbvia baseada em conjunto (por exemplo, usando um conjunto de bits". O segundo último parágrafo da pergunta original.
hrnt
9
@hmt: Sim, a pergunta foi editada há alguns minutos atrás. Estou apenas dando a resposta, que eu esperaria de um entrevistado ... Construir artificialmente uma solução abaixo do ideal (você não pode superar o tempo O (n) + O (k), não importa o que você faça) ' não faz sentido para mim - exceto se você não puder pagar O (n) espaço adicional, mas a pergunta não está explícita nisso.
Chris Lercher
3
Eu editei a pergunta novamente para esclarecer melhor. Eu aprecio o feedback / resposta.
polygenelubricants
33

Não verifiquei a matemática, mas suspeito que a computação Σ(n^2)no mesmo passo em que calculamos Σ(n)forneceria informações suficientes para obter dois números ausentes, faça Σ(n^3)o mesmo se houver três e assim por diante.

AakashM
fonte
15

O problema com soluções baseadas em somas de números é que elas não levam em conta o custo de armazenar e trabalhar com números com grandes expoentes ... na prática, para que funcione para n muito grande, seria usada uma biblioteca de grandes números . Podemos analisar a utilização do espaço para esses algoritmos.

Podemos analisar a complexidade de tempo e espaço dos algoritmos sdcvvc e Dimitris Andreou.

Armazenamento:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

assim l_j \in \Theta(j log n)

Armazenamento total usado: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Espaço utilizado: assumindo que a computação a^jleva ceil(log_2 j)tempo, tempo total:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Tempo total usado: \Theta(kn log n)

Se esse tempo e espaço forem satisfatórios, você pode usar um algoritmo recursivo simples. Seja b! A i-ésima entrada na sacola, no número de números antes das remoções ek no número de remoções. Na sintaxe Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Armazenamento usado: O(k)para lista, O(log(n))para pilha: O(k + log(n)) esse algoritmo é mais intuitivo, tem a mesma complexidade de tempo e usa menos espaço.

a1kmm
fonte
1
+1, parece bom, mas você me perdeu da linha 4 para a linha 5 no snippet # 1 - você poderia explicar isso mais? Obrigado!
Jrandom_hacker 28/10/10
isInRangeé O (log n) , não O (1) : compara números no intervalo 1..n, portanto, ele precisa comparar os bits O (log n) . Não sei até que ponto esse erro afeta o restante da análise.
Jcsahnwaldt diz GoFundMonica
14

Espere um minuto. Como a pergunta é declarada, há 100 números na sacola. Não importa o tamanho de k, o problema pode ser resolvido em tempo constante, porque você pode usar um conjunto e remover números do conjunto em no máximo 100 k de iterações de um loop. 100 é constante. O conjunto de números restantes é a sua resposta.

Se generalizarmos a solução para os números de 1 a N, nada muda, exceto N não é uma constante, então estamos no tempo O (N - k) = O (N). Por exemplo, se usarmos um conjunto de bits, configuramos os bits para 1 em O (N), iteramos pelos números, configurando os bits para 0 à medida que avançamos (O (Nk) = O (N)) e depois tem a resposta.

Parece-me que o entrevistador estava perguntando como imprimir o conteúdo do conjunto final no tempo O (k) em vez do tempo O (N). Claramente, com um pouco definido, você precisa percorrer todos os N bits para determinar se deve imprimir o número ou não. No entanto, se você alterar a maneira como o aparelho é implementado, poderá imprimir os números em k iterações. Isso é feito colocando os números em um objeto a ser armazenado em um conjunto de hash e em uma lista duplamente vinculada. Quando você remove um objeto do conjunto de hash, também o remove da lista. As respostas serão deixadas na lista que agora tem o comprimento k.

JeremyP
fonte
9
Essa resposta é muito simples e todos sabemos que respostas simples não funcionam! ;) Porém, seriamente, a pergunta original provavelmente deveria enfatizar o requisito de espaço O (k).
DK.
O problema não é simples, mas você precisará usar O (n) memória adicional para o mapa. O busto problema me resolvido em tempo constante e memória constante
Mojo Risin
3
Aposto que você pode provar que a solução mínima é pelo menos O (N). porque menos, significaria que você nem sequer olhou para alguns números e, como não há pedidos especificados, é obrigatório olhar TODOS os números.
precisa saber é o seguinte
Se considerarmos a entrada como um fluxo e n for muito grande para manter na memória, o requisito de memória O (k) fará sentido. Ainda podemos usar o hash: Apenas faça k ^ 2 buckets e use o algoritmo de soma simples em cada um deles. Isso é apenas memória k ^ 2 e mais alguns buckets podem ser usados ​​para obter alta probabilidade de sucesso.
22416 Thomas Ahle
8

Para resolver a questão de 2 (e 3) números ausentes, você pode modificar quickselect, que em média é executado O(n)e usa memória constante se o particionamento for feito no local.

  1. Particione o conjunto com relação a um pivô aleatório pem partições l, que contêm números menores que o pivô e r, que contêm números maiores que o pivô.

  2. Determine em quais partições os 2 números ausentes estão comparando o valor de pivô ao tamanho de cada partição ( p - 1 - count(l) = count of missing numbers in le n - count(r) - p = count of missing numbers in r)

  3. a) Se estiver faltando um número em cada partição, use a abordagem da diferença de somas para encontrar cada número que falta.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 e ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) Se uma partição está faltando os dois números e a partição está vazia, então os números ausentes estão (p-1,p-2)ou (p+1,p+2) dependem de qual partição está faltando os números.

    Se uma partição estiver faltando 2 números, mas não estiver vazia, recorra a essa partição.

Com apenas 2 números ausentes, esse algoritmo sempre descarta pelo menos uma partição, mantendo a O(n)complexidade do tempo médio da seleção rápida. Da mesma forma, com 3 números ausentes, esse algoritmo também descarta pelo menos uma partição a cada passagem (porque, como 2 números ausentes, no máximo apenas 1 partição conterá vários números ausentes). No entanto, não tenho certeza de quanto o desempenho diminui quando mais números ausentes são adicionados.

Aqui está uma implementação que não usa particionamento no local, portanto, este exemplo não atende aos requisitos de espaço, mas ilustra as etapas do algoritmo:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo

FuzzyTree
fonte
Particionar o conjunto é como usar espaço linear. Pelo menos, não funcionaria em uma configuração de streaming.
22416 Thomas Ahle
@ThomasAhle, consulte en.wikipedia.org/wiki/Selection_algorithm#Space_complexity . particionar o conjunto no lugar requer apenas O (1) espaço adicional - não espaço linear. Em uma configuração de streaming, seria O (k) espaço adicional; no entanto, a pergunta original não menciona o streaming.
FuzzyTree
Não diretamente, mas ele escreve "você deve escanear a entrada em O (N), mas você pode capturar apenas uma pequena quantidade de informação (definida em termos de k e não N)", que geralmente é a definição de streaming. Mover todos os números para particionamento não é realmente possível, a menos que você tenha uma matriz de tamanho N. É apenas que a pergunta tem muitas respostas, que parecem ignorar essa restrição.
22416 Thomas Ahle
1
Mas, como você diz, o desempenho pode diminuir à medida que mais números são adicionados? Também podemos usar o algoritmo da mediana linear do tempo, para obter sempre um corte perfeito, mas se os números k estiverem bem distribuídos em 1, ..., n, você não precisará aumentar os níveis de logk "profundamente" antes de podar algum ramo?
22416 Thomas Ahle
2
O pior dos casos é o nlogk, porque você precisa processar toda a entrada na maioria das vezes, e é uma sequência geométrica (que começa com no máximo n elementos). Os requisitos de espaço são registrados quando implementados com recursão simples, mas podem ser feitos O (1) executando uma seleção rápida real e garantindo o comprimento correto de cada partição.
Emu #
7

Aqui está uma solução que usa k bits de armazenamento extra, sem truques inteligentes e simples. Tempo de execução O (n), espaço extra O (k). Apenas para provar que isso pode ser resolvido sem ler a solução primeiro ou ser um gênio:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}
gnasher729
fonte
Você queria (data [n - 1 - odd] % 2 == 1) ++odd;?
Charles
2
Você poderia explicar como isso funciona? Eu não entendo
Teepeemm 26/09/14
A solução seria muito, muito simples se eu pudesse usar uma matriz de (n + k) booleanos para armazenamento temporário, mas isso não é permitido. Então, reorganizo os dados, colocando os números pares no início e os números ímpares no final da matriz. Agora, os bits mais baixos desses n números podem ser usados ​​para armazenamento temporário, porque eu sei quantos números pares e ímpares existem e podem reconstruir os bits mais baixos! Esses n bits ek bits extras são exatamente os booleanos (n + k) que eu precisava.
gnasher729
2
Isso não funcionaria se os dados fossem muito grandes para serem armazenados na memória e você só o visse como um fluxo. Deliciosamente embora hacky :)
Thomas Ahle
A complexidade do espaço pode ser O (1). Em uma primeira passagem, você processa todos os números <(n - k) exatamente por esse algoritmo, sem usar 'extra'. Em uma segunda passagem, você limpa os bits de paridade novamente e usa as primeiras posições k para indexar números (nk) .. (n).
emu
5

Você pode verificar se todos os números existem? Se sim, você pode tentar o seguinte:

S = soma de todos os números na sacola (S <5050)
Z = soma dos números ausentes 5050 - S

se os números ausentes forem xe yentão:

x = Z - y e
max (x) = Z - 1

Então você verificar o intervalo de 1para max(x)e encontrar o número

Ilian Iliev
fonte
1
O que max(x)significa quando xé um número?
22416 Thomas Ahle
2
ele provavelmente significa máximo do conjunto de números
JavaHopper
se tivermos mais de 2 números, esta solução será eliminada
ozgeneral 29/01
4

Pode ser que esse algoritmo possa funcionar para a pergunta 1:

  1. Pré-calcule xor dos 100 primeiros números inteiros (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. xou os elementos conforme eles continuam vindo do fluxo de entrada (val1 = val1 ^ next_input)
  3. resposta final = val ^ val1

Ou melhor ainda:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Na verdade, esse algoritmo pode ser expandido para dois números ausentes. O primeiro passo permanece o mesmo. Quando chamamos GetValue com dois números ausentes, o resultado será a a1^a2são os dois números ausentes. Digamos

val = a1^a2

Agora, para peneirar a1 e a2 de val, pegamos qualquer bit definido em val. Vamos dizer que o ithbit está definido em val. Isso significa que a1 e a2 têm paridade diferente na ithposição do bit. Agora fazemos outra iteração na matriz original e mantemos dois valores xor. Um para os números que têm o i-bit definido e outro que não tem o i-bit definido. Agora temos dois baldes de números, e é garantido que a1 and a2estarão em baldes diferentes. Agora repita o mesmo que fizemos para encontrar um elemento ausente em cada um dos buckets.

bashrc
fonte
Isso apenas resolve o problema k=1, certo? Mas eu gosto de usar xorsomas, parece um pouco mais rápido.
22416 Thomas Ahle
@ThomasAhle Yes. Eu chamei isso na minha resposta.
bashrc
Direita. Você tem uma idéia de como pode ser uma "segunda ordem" xor, para k = 2? Semelhante ao uso de quadrados para soma, poderíamos "quadrado" para xor?
Thomas Ahle
1
@ThomasAhle Modificado para funcionar com 2 números ausentes.
bashrc 4/16
esta é a minha maneira favorita :)
robert king
3

Você pode resolver o Q2 se tiver a soma de ambas as listas e o produto de ambas.

(l1 é o original, l2 é a lista modificada)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Podemos otimizar isso, pois a soma de uma série aritmética é n vezes a média do primeiro e do último termos:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Agora sabemos que (se aeb são os números removidos):

a + b = d
a * b = m

Para que possamos reorganizar para:

a = s - b
b * (s - b) = m

E multiplique:

-b^2 + s*b = m

E reorganize para que o lado direito seja zero:

-b^2 + s*b - m = 0

Então podemos resolver com a fórmula quadrática:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Exemplo de código Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Não conheço a complexidade do sqrt, reduzi e soquei as funções, por isso não consigo descobrir a complexidade desta solução (se alguém souber, por favor, comente abaixo).

Tuomas Laakkonen
fonte
Quanto tempo e memória ele usa para calcular x1*x2*x3*...?
21416 Thomas Ahle
@ThomasAhle É o tempo O (n) e O (1) no comprimento da lista, mas, na realidade, é mais como multiplicação (pelo menos em Python) é O (n ^ 1.6) tempo no comprimento de o número e os números têm espaço O (log n) em seu comprimento.
Tuomas Laakkonen 29/04
@ThomasAhle Não, log (a ^ n) = n * log (a) para que você tenha espaço O (l log k) para armazenar o número. Portanto, dada uma lista de comprimento le números originais de comprimento k, você teria espaço O (l), mas o fator constante (log k) seria menor do que apenas escrever todos eles. (Eu não acho que o meu método é particularmente boa maneira de responder à pergunta.)
Tuomas Laakkonen
3

Para o Q2, essa é uma solução um pouco mais ineficiente que as outras, mas ainda possui tempo de execução O (N) e ocupa espaço O (k).

A idéia é executar o algoritmo original duas vezes. No primeiro, você obtém um número total que está faltando, o que fornece um limite superior para os números ausentes. Vamos ligar para este número N. Você sabe que os dois números ausentes serão somados N; portanto, o primeiro número só pode estar no intervalo [1, floor((N-1)/2)]enquanto o segundo está [floor(N/2)+1,N-1].

Assim, você executa um loop em todos os números mais uma vez, descartando todos os números que não estão incluídos no primeiro intervalo. Os que são, você acompanha a soma deles. Por fim, você conhecerá um dos dois números ausentes e, por extensão, o segundo.

Tenho a sensação de que esse método pode ser generalizado e talvez várias pesquisas sejam executadas em "paralelo" durante uma única passagem pela entrada, mas ainda não descobri como.

Svalorzen
fonte
Ah, sim, essa é a mesma solução que eu criei para o segundo trimestre, apenas com o cálculo da soma novamente levando os negativos para todos os números abaixo de N / 2, mas isso é ainda melhor!
precisa saber é
2

Eu acho que isso pode ser feito sem quaisquer equações e teorias matemáticas complexas. Abaixo está uma proposta para uma solução no local e com complexidade de tempo O (2n):

Suposições do formulário de entrada:

Nº de números na bolsa = n

Nº de números ausentes = k

Os números na sacola são representados por uma matriz de comprimento n

Comprimento da matriz de entrada para o algo = n

As entradas ausentes na matriz (números retirados da sacola) são substituídas pelo valor do primeiro elemento na matriz.

Por exemplo. Inicialmente, o saco se parece com [2,9,3,7,8,6,4,5,1,10]. Se 4 for retirado, o valor de 4 se tornará 2 (o primeiro elemento da matriz). Portanto, depois de tirar 4, a bolsa ficará com [2,9,3,7,8,6,2,5,1,10]

A chave para esta solução é marcar o ÍNDICE de um número visitado, negando o valor nesse ÍNDICE à medida que a matriz é percorrida.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }
pickhunter
fonte
Isso usa muita memória.
Thomas Ahle
2

Existe uma maneira geral de generalizar algoritmos de streaming como este. A idéia é usar um pouco de randomização para "espalhar" os kelementos em subproblemas independentes, onde nosso algoritmo original resolve o problema para nós. Essa técnica é usada na reconstrução de sinais esparsos, entre outras coisas.

  • Faça uma matriz ade tamanho u = k^2.
  • Escolha qualquer função hash universal , h : {1,...,n} -> {1,...,u}. (Como turno múltiplo )
  • Para cada iem 1, ..., naumentoa[h(i)] += i
  • Para cada número xno fluxo de entrada, diminua a[h(x)] -= x.

Se todos os números ausentes tiverem um hash em intervalos diferentes, os elementos diferentes de zero da matriz agora conterão os números ausentes.

A probabilidade de um determinado par ser enviado para o mesmo bucket é menor do que 1/upor definição de uma função hash universal. Como existem k^2/2pares, temos que a probabilidade de erro seja no máximo k^2/2/u=1/2. Ou seja, obtemos sucesso com probabilidade de pelo menos 50% e, se aumentarmos u, aumentamos nossas chances.

Observe que esse algoritmo ocupa k^2 lognbits de espaço (precisamos de lognbits por intervalo de array). Isso corresponde ao espaço exigido pela resposta de @Dimitris Andreou (em particular, o requisito de espaço da fatoração polinomial, que também é randomizado.) Esse algoritmo também tem constante tempo por atualização, em vez de tempo kno caso de somas de energia.

De fato, podemos ser ainda mais eficientes do que o método da soma de potência, usando o truque descrito nos comentários.

Thomas Ahle
fonte
Nota: Também podemos usar xorem cada balde, se não sumfor mais rápido em nossa máquina.
21416 Thomas Ahle
Interessante, mas acho que isso só respeita a restrição de espaço quando k <= sqrt(n)- pelo menos se u=k^2? Suponha que k = 11 e n = 100, então você teria 121 buckets e o algoritmo acabaria sendo semelhante a ter uma matriz de 100 bits que você desmarca ao ler cada # do fluxo. Aumentar uaumenta as chances de sucesso, mas há um limite para quanto você pode aumentá-lo antes de exceder a restrição de espaço.
FuzzyTree 27/04/16
1
O problema faz mais sentido para nmuito maior do que k, eu acho, mas você pode reduzir o espaço k logncom um método muito semelhante ao hash descrito, enquanto mantém atualizações constantes de tempo. É descrito em gnunet.org/eppstein-set-reconciliation , como o método da soma das potências, mas basicamente você faz hash em 'dois de k' buckets com uma forte função hash como tabulation hashing, o que garante que algum bucket terá apenas um elemento . Para decodificar, identifica essa balde e remove o elemento de ambos os seus baldes, que (provavelmente) libera outro balde e assim por diante
Thomas Ahle
2

Uma solução muito simples para o segundo trimestre, que estou surpresa que ninguém tenha respondido. Use o método da Q1 para encontrar a soma dos dois números ausentes. Vamos denotá-lo por S, então um dos números ausentes é menor que S / 2 e o outro é maior que S / 2 (duh). Soma todos os números de 1 a S / 2 e compare-o com o resultado da fórmula (da mesma forma que no método Q1) para encontrar o menor entre os números ausentes. Subtraia-o de S para encontrar o maior número ausente.

Gilad Deutsch
fonte
Eu acho que isso é o mesmo que a resposta de Svalorzen , mas você explicou em palavras melhores. Tem alguma idéia de como generalizá-lo para Qk?
John McClane
Desculpe por ter perdido a outra resposta. Não tenho certeza se é possível generalizá-lo para $ Q_k $, pois nesse caso você não pode vincular o menor elemento ausente a algum intervalo. Você sabe que algum elemento deve ser menor que $ S / k $, mas isso pode ser verdadeiro para vários elementos
Gilad Deutsch
1

Problema muito bom. Eu usaria uma diferença definida para Qk. Muitas linguagens de programação ainda têm suporte para isso, como no Ruby:

missing = (1..100).to_a - bag

Provavelmente não é a solução mais eficiente, mas é uma que eu usaria na vida real se me desse conta de uma tarefa nesse caso (limites conhecidos, limites baixos). Se o conjunto de números fosse muito grande, eu consideraria um algoritmo mais eficiente, é claro, mas até então a solução simples seria suficiente para mim.

DarkDust
fonte
1
Isso usa muito espaço.
21416 Thomas Ahle
@ThomasAhle: Por que você está adicionando comentários inúteis a cada segunda resposta? O que você quer dizer com usar muito espaço?
precisa saber é o seguinte
Porque a pergunta diz que "não podemos permitir nenhum espaço adicional proporcional a N." Esta solução faz exatamente isso.
22416 Thomas Ahle
1

Você pode tentar usar um filtro Bloom . Insira cada número no saco na flor e, em seguida, repita o conjunto completo de 1k até relatar que cada um não foi encontrado. Isso pode não encontrar a resposta em todos os cenários, mas pode ser uma solução boa o suficiente.

jdizzle
fonte
Há também o filtro de contagem florida, que permite a exclusão. Depois, basta adicionar todos os números e excluir os que você vê no fluxo.
Thomas Ahle
Haha, essa é provavelmente uma das respostas mais práticas, mas recebe pouca atenção.
Ldog 26/05/19
1

Eu adotaria uma abordagem diferente para essa pergunta e sondaria o entrevistador para obter mais detalhes sobre o problema maior que ele está tentando resolver. Dependendo do problema e dos requisitos que o cercam, a solução óbvia baseada em conjunto pode ser a coisa certa e a abordagem gerar-uma-lista-e-escolher-depois-depois.

Por exemplo, pode ser que o entrevistador despache nmensagens e precise saber o kque não resultou em uma resposta e precise conhecê-la no menor tempo possível após o relógion-k resposta. Digamos também que a natureza do canal de mensagens é tal que, mesmo funcionando em plena capacidade, há tempo suficiente para processar as mensagens sem afetar o tempo necessário para produzir o resultado final após a chegada da última resposta. Esse tempo pode ser usado para inserir algumas facetas identificadoras de cada mensagem enviada em um conjunto e excluí-la quando cada resposta correspondente chegar. Depois que a última resposta chega, a única coisa a ser feita é remover seu identificador do conjunto, o que em implementações típicas levaO(log k+1). Depois disso, o conjunto contém a lista de kelementos ausentes e não há processamento adicional a ser feito.

Essa certamente não é a abordagem mais rápida para processar lotes de números pré-gerados, porque tudo funciona O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Mas funciona com qualquer valor de k(mesmo que não seja conhecido antecipadamente) e, no exemplo acima, foi aplicado de maneira a minimizar o intervalo mais crítico.

Blrfl
fonte
Isso funcionaria se você tivesse apenas O (k ^ 2) memória extra?
Thomas Ahle
1

Você pode motivar a solução pensando nela em termos de simetrias (grupos, na linguagem matemática). Não importa a ordem do conjunto de números, a resposta deve ser a mesma. Se você for usar kfunções para ajudar a determinar os elementos ausentes, pense em quais funções têm essa propriedade: simétrica. A função s_1(x) = x_1 + x_2 + ... + x_né um exemplo de função simétrica, mas existem outras de maior grau. Em particular, considere as funções simétricas elementares . A função simétrica elementar do grau 2 é s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_na soma de todos os produtos de dois elementos. Da mesma forma, para as funções simétricas elementares de grau 3 e superior. Eles são obviamente simétricos. Além disso, eles são os blocos de construção para todas as funções simétricas.

Você pode criar as funções simétricas elementares conforme observa isso s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Uma reflexão mais aprofundada deve convencê-lo disso s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))e assim por diante, para que eles possam ser computados de uma só vez.

Como podemos saber quais itens estavam faltando na matriz? Pense no polinômio (z-x_1)(z-x_2)...(z-x_n). Ele avalia 0se você inseriu algum dos números x_i. Expandindo o polinômio, você entende z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. As funções simétricas elementares também aparecem aqui, o que não é realmente uma surpresa, uma vez que o polinômio deve permanecer o mesmo se aplicarmos alguma permutação nas raízes.

Assim, podemos construir o polinômio e tentar fatorá-lo para descobrir quais números não estão no conjunto, como outros já mencionaram.

Por fim, se estivermos preocupados com o transbordamento de memória com grandes números (o enésimo polinômio simétrico será da ordem 100!), podemos fazer esses cálculos mod ponde pé um primo maior que 100. Nesse caso, avaliamos o polinômio mod pe descobrimos que ele novamente avalia para 0quando a entrada é um número no conjunto e é avaliado como um valor diferente de zero quando a entrada é um número que não está no conjunto. No entanto, como outros já apontaram, para obter os valores do polinômio no tempo que depende k, não N, precisamos fatorar o polinômio mod p.

Edward Doolittle
fonte
1

Outra maneira é usar a filtragem de gráfico residual.

Suponha que temos os números 1 a 4 e 3 está faltando. A representação binária é a seguinte,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

E eu posso criar um fluxograma como o seguinte.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Observe que o gráfico de fluxo contém x nós, enquanto x é o número de bits. E o número máximo de arestas é (2 * x) -2.

Portanto, para números inteiros de 32 bits, será necessário espaço O (32) ou O (1).

Agora, se eu remover a capacidade de cada número a partir de 1,2,4, resta um gráfico residual.

0 ----------> 1 ---------> 1

Por fim, executarei um loop como o seguinte,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Agora, o resultado está em resultnúmeros que também não estão faltando (falso positivo). Mas o <= (tamanho do resultado) <= n quando há kelementos ausentes.

Vou percorrer a lista fornecida uma última vez para marcar o resultado como ausente ou não.

Portanto, a complexidade do tempo será O (n).

Finalmente, é possível reduzir o número de falsos positivos (e o espaço necessário), tendo nós 00, 01, 11, 10em vez de apenas 0e 1.

shuva
fonte
Eu não entendo o seu diagrama gráfico. O que os nós, arestas e números representam? Por que algumas das arestas são direcionadas e outras não?
dain
Na verdade, eu realmente não entendo sua resposta, você pode esclarecer um pouco mais?
dain
1

Você provavelmente precisaria de esclarecimentos sobre o que O (k) significa.

Aqui está uma solução trivial para k arbitrário: para cada v em seu conjunto de números, acumule a soma de 2 ^ v. No final, o loop i de 1 a N. Se a soma AND bit a bit com 2 ^ i for zero, então i estará ausente. (Ou numericamente, se o piso da soma dividida por 2 ^ i for par sum modulo 2^(i+1)) < 2^i.)

Fácil né? Tempo O (N), armazenamento O (1) e suporta k arbitrário.

Só que você está computando números enormes que, em um computador real, exigiriam espaço O (N). De fato, esta solução é idêntica a um vetor de bits.

Portanto, você pode ser inteligente e calcular a soma, a soma dos quadrados e a soma dos cubos ... até a soma de v ^ k, e fazer as matemáticas sofisticadas para extrair o resultado. Mas esses também são grandes números, o que levanta a questão: de que modelo abstrato de operação estamos falando? Quanto cabe no espaço O (1) e quanto tempo leva para resumir números do tamanho que você precisar?

sfink
fonte
Boa resposta! Uma coisinha: "Se sum modulo 2 ^ i for zero, então i está ausente" está incorreto. Mas está claro o que se pretende. Eu acho que "se a soma do módulo 2 ^ (i + 1) for menor que 2 ^ i, então eu falta" estaria correto. (É claro que, na maioria das linguagens de programação usaríamos bit deslocando em vez de cálculo modulo Às vezes linguagens de programação são um pouco mais expressiva do que a notação matemática habitual :-)..)
jcsahnwaldt diz GoFundMonica
1
Obrigado, você está totalmente certo! Corrigido, apesar de eu ser preguiçoso e desviado da notação matemática ... ah, e eu estraguei tudo também. Fixação de novo ...
sfink
1

Aqui está uma solução que não depende de matemática complexa como as respostas de sdcvvc / Dimitris Andreou, não altera a matriz de entrada como caf e o Coronel Panic, e não usa o conjunto de bits de tamanho enorme como Chris Lercher, JeremyP e muitos outros fizeram. Basicamente, comecei com a ideia de Svalorzen / Gilad Deutch para o Q2, generalizei para o caso comum Qk e implementei em Java para provar que o algoritmo funciona.

A ideia

Suponha que tenhamos um intervalo arbitrário I, do qual sabemos apenas que ele contém pelo menos um dos números ausentes. Após uma passagem através do feixe de entrada, olhando apenas para os números de Eu , que pode obter tanto a soma S e a quantidade Q de números em falta a partir de I . Fazemos isso simplesmente diminuindo o comprimento de I toda vez que encontramos um número de I (para obter Q ) e diminuindo a soma pré-calculada de todos os números em I pelo número encontrado toda vez (para obter S ).

Agora vamos olhar para S e Q . Se Q = 1 , isto significa que, em seguida, que contém apenas um dos números que faltam, e este número é claramente S . Marcamos I como concluído (é chamado de "inequívoco" no programa) e o deixamos de fora de uma análise mais aprofundada. Por outro lado, se Q> 1 , podemos calcular a média A = S / Q de números que faltam contida no I . Como todos os números são distintas, pelo menos uma de tais números é estritamente inferior a um e pelo menos um é estritamente maior que um . Agora dividimos eu em Aem dois intervalos menores, cada um dos quais contém pelo menos um número ausente. Observe que não importa a qual dos intervalos atribuímos A , caso seja um número inteiro.

Fazemos a próxima matriz passar calculando S e Q para cada um dos intervalos separadamente (mas na mesma passagem) e depois marcar intervalos com Q = 1 e dividir intervalos com Q> 1 . Continuamos esse processo até que não haja novos intervalos "ambíguos", ou seja, não temos nada para dividir porque cada intervalo contém exatamente um número ausente (e sempre o conhecemos porque conhecemos S ). Começamos a partir do único intervalo "todo o intervalo", contendo todos os números possíveis (como [1..N] na pergunta).

Análise de complexidade de tempo e espaço

O número total de passes p que precisamos fazer até o processo parar nunca é maior do que os números ausentes contam k . A desigualdade p <= k pode ser comprovada rigorosamente. Por outro lado, também existe um limite superior empírico p <log 2 N + 3 que é útil para grandes valores de k . Precisamos fazer uma pesquisa binária para cada número da matriz de entrada para determinar o intervalo ao qual ela pertence. Isso adiciona o multiplicador de log k à complexidade do tempo.

No total, a complexidade do tempo é O (N ᛫ min (k, log N) ᛫ log k) . Observe que, para k grande , isso é significativamente melhor que o método do sdcvvc / Dimitris Andreou, que é O (N ᛫ k) .

Por seu trabalho, o algoritmo requer O (k) espaço adicional para armazenar na maioria dos intervalos de k , o que é significativamente melhor que O (N) em soluções de "bitset".

Implementação Java

Aqui está uma classe Java que implementa o algoritmo acima. Ele sempre retorna uma matriz classificada de números ausentes. Além disso, ele não requer que os números ausentes contem k, porque o calcula na primeira passagem. Todo o intervalo de números é dado pelos parâmetros minNumbere maxNumber(por exemplo, 1 e 100 para o primeiro exemplo da pergunta).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Para ser justo, essa classe recebe entrada na forma de NumberBagobjetos. NumberBagnão permite modificação de matriz e acesso aleatório e também conta quantas vezes a matriz foi solicitada para deslocamento sequencial. Também é mais adequado para testes de grandes matrizes do que Iterable<Integer>porque evita o encaixe de intvalores primitivos e permite envolver uma parte de um grande int[]para uma preparação de teste conveniente. Não é difícil substituir, se desejado, NumberBagpor int[]ou Iterable<Integer>digitar a findassinatura, alterando dois loops for para lo em foreach.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Testes

Exemplos simples que demonstram o uso dessas classes são dados abaixo.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

O teste de grandes matrizes pode ser realizado desta maneira:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Experimente-os no Ideone

John McClane
fonte
0

Acredito que tenho um algoritmo de O(k)tempo e O(log(k))espaço, já que você tem as funções floor(x)e log2(x)para números inteiros arbitrariamente grandes disponíveis:

Você tem um knúmero inteiro longo de bits (daí o log8(k)espaço) onde você adiciona o x^2, onde x é o próximo número que você encontra na sacola: s=1^2+2^2+...isso leva O(N)tempo (o que não é um problema para o entrevistador). No final, você obtém j=floor(log2(s))qual é o maior número que você está procurando. Então, s=s-je você faz novamente o acima:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Agora, você normalmente não possui as funções floor e log2 para 2756números inteiros -bit, mas sim para duplos. Assim? Simplesmente, para cada 2 bytes (ou 1, 3 ou 4), você pode usar essas funções para obter os números desejados, mas isso adiciona um O(N)fator à complexidade do tempo

CostasGR43
fonte
0

Isso pode parecer estúpido, mas, no primeiro problema apresentado a você, você precisaria ver todos os números restantes na sacola para adicioná-los e encontrar o número que falta usando essa equação.

Portanto, como você vê todos os números, procure o número que está faltando. O mesmo vale para quando faltam dois números. Bem simples, eu acho. Não faz sentido usar uma equação quando você vê os números restantes na sacola.

Stephan M
fonte
2
Acho que o benefício de resumir é que você não precisa se lembrar de quais números já viu (por exemplo, não há necessidade de memória extra). Caso contrário, a única opção é manter um conjunto de todos os valores vistos e iterar sobre esse conjunto novamente para encontrar o que está faltando.
Dan Tao
3
Essa pergunta geralmente é feita com a estipulação da complexidade do espaço O (1).
A soma dos primeiros N números é N (N + 1) / 2. Para N = 100, Soma = 100 * (101) / 2 = 5050;
tmarthal
0

Eu acho que isso pode ser generalizado assim:

Denota S, M como os valores iniciais para a soma das séries aritméticas e multiplicação.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Eu deveria pensar em uma fórmula para calcular isso, mas esse não é o ponto. De qualquer forma, se um número estiver faltando, você já forneceu a solução. No entanto, se dois números estiverem ausentes, vamos denotar a nova soma e o múltiplo total por S1 e M1, que serão os seguintes:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Como você conhece S1, M1, M e S, a equação acima é solucionável para encontrar aeb, os números ausentes.

Agora, para os três números ausentes:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Agora o seu desconhecido é 3, enquanto você só tem duas equações que você pode resolver.

Jack_of_All_Trades
fonte
A multiplicação fica bastante grande. Além disso, como você generaliza para mais de 2 números ausentes?
21416 Thomas Ahle
Eu tentei essas fórmulas em uma sequência muito simples com N = 3 e números ausentes = {1, 2}. Não funcionei, pois acredito que o erro está nas fórmulas (2) que devem ser lidas M1 = M / (a * b)(veja a resposta ). Então funciona bem.
dma_k 2/09/16
0

Não sei se isso é eficiente ou não, mas gostaria de sugerir esta solução.

  1. Calcular xor dos 100 elementos
  2. Calcular xor dos 98 elementos (depois que os 2 elementos são removidos)
  3. Agora (resultado de 1) XOR (resultado de 2) fornece o xor dos dois números ausentes i..ea XOR b se aeb são os elementos ausentes
    4.Get a soma dos números ausentes com sua abordagem usual do soma fórmula diff e vamos dizer que o diff é d.

Agora execute um loop para obter os pares possíveis (p, q), ambos em [1, 100] e somar em d.

Quando um par é obtido, verifique se (resultado de 3) XOR p = q e se sim, terminamos.

Corrija-me se estiver errado e também comente a complexidade do tempo, se estiver correto

user2221214
fonte
2
Não acho que a soma e o xor definam exclusivamente dois números. Executar um loop para obter todas as k-tuplas possíveis que somam d leva tempo O (C (n, k-1)) = O (n <sup> k-1 </sup>), que, para k> 2, é ruim.
Teepeemm
0

Podemos fazer o Q1 e Q2 em O (log n) na maioria das vezes.

Suponha que nosso memory chipconsiste em matriz de nnúmero de test tubes. E um número xno tubo de ensaio é representado por x milliliterde químico-líquido.

Suponha que nosso processador seja a laser light. Quando acendemos o laser, ele atravessa todos os tubos perpendicularmente ao seu comprimento. Sempre que passa pelo líquido químico, a luminosidade é reduzida em 1. E passar a luz em uma marca de mililitro é uma operação de O(1).

Agora, se acendermos o laser no meio do tubo de ensaio e obtermos a saída de luminosidade

  • é igual a um valor pré-calculado (calculado quando nenhum número estava faltando), então os números ausentes são maiores que n/2.
  • Se nossa saída for menor, haverá pelo menos um número ausente menor que n/2. Também podemos verificar se a luminosidade é reduzida em 1ou 2. se for reduzido 1, um número ausente será menor que n/2e outro será maior que n/2. Se for reduzido 2, os dois números serão menores que n/2.

Podemos repetir o processo acima várias vezes, restringindo nosso domínio de problemas. Em cada etapa, reduzimos o domínio pela metade. E, finalmente, podemos chegar ao nosso resultado.

Algoritmos paralelos que merecem ser mencionados (por serem interessantes),

  • classificando por algum algoritmo paralelo, por exemplo, a mesclagem paralela pode ser feita no O(log^3 n)tempo. E então o número ausente pode ser encontrado por busca binária no O(log n)tempo.
  • Teoricamente, se tivermos nprocessadores, cada processo poderá verificar uma das entradas e definir algum sinalizador que identifique o número (convenientemente em uma matriz). E na próxima etapa, cada processo pode verificar cada sinalizador e finalmente gerar o número que não está sinalizado. Todo o processo levará O(1)tempo. Possui O(n)requisitos adicionais de espaço / memória.

Observe que os dois algoritmos paralelos fornecidos acima podem precisar de espaço adicional, conforme mencionado no comentário .

shuva
fonte
Embora o método do tubo de ensaio com laser seja realmente interessante, espero que você concorde que não se traduz bem nas instruções de hardware e é improvável que esteja O(logn)em um computador.
SirGuy
1
Quanto ao seu método de classificação, isso exigirá uma quantidade de espaço extra que depende Ne mais do que O(N)tempo (em termos de dependência N), da qual pretendemos fazer melhor.
SirGuy
@SirGuy Agradeço sua preocupação com o conceito de tubo de ensaio e o custo da memória de processamento paralelo. Minha postagem é para compartilhar meus pensamentos sobre o problema. Os processadores GPU agora estão possibilitando o processamento paralelo. Quem sabe, se o conceito de tubo de ensaio não estiver disponível no futuro.
shuva