Encontre um “buraco” em uma lista de números

14

Qual é a maneira mais rápida de encontrar o primeiro inteiro (menor) que não existe em uma determinada lista de números inteiros não-classificados (e que é maior que o menor valor da lista)?

Minha abordagem primitiva é classificá-los e percorrer a lista, existe uma maneira melhor?

    
por Fabian Zeindl 24.04.2012 / 18:27
fonte

8 respostas

29

Assumindo que você quer dizer "inteiro" quando diz "número", você pode usar um bitvector de tamanho 2 ^ n, onde n é o número de elementos (digamos, seu intervalo inclui inteiros entre 1 e 256, então você pode usar um bitvector de 256 bits ou 32 bytes). Quando você se deparar com um número inteiro na posição n do seu alcance, defina o enésimo bit.

Quando você terminar de enumerar a coleção de inteiros, você iterará os bits em seu bitvector, procurando pela posição de qualquer bit definido como 0. Eles agora correspondem à posição n de seu (s) número (s) inteiro (s) ausente (s). >

Isto é O (2 * N), portanto O (N) e provavelmente mais memória eficiente do que ordenar toda a lista.

    
por 24.04.2012 / 18:45
fonte
4

Se você classificar a lista inteira primeiro, garante o pior tempo de execução. Além disso, seu algoritmo de escolha de classificação é crítico.

Veja como eu abordaria esse problema:

  1. Use um tipo de heap , concentrando-se nos elementos menores da lista.
  2. Após cada troca, veja se você tem uma lacuna.
  3. Se você encontrar uma lacuna, então return : Você encontrou sua resposta.
  4. Se você não encontrar uma lacuna, continue trocando.

Veja uma visualização de um tipo de pilha .

    
por 24.04.2012 / 18:53
fonte
3

Apenas para ser esotérico e "inteligente", no caso especial do array ter apenas um "buraco", você pode tentar uma solução baseada em XOR:

  • Determine o intervalo de sua matriz; isso é feito definindo-se uma variável "max" e "min" para o primeiro elemento da matriz e, para cada elemento depois disso, se esse elemento for menor que o mínimo ou maior que o máximo, defina min ou max como novo valor.
  • Se o intervalo for um a menos que a cardinalidade do conjunto, existe apenas um "furo" para que você possa usar o XOR.
  • Inicialize uma variável inteira X a zero.
  • Para cada inteiro de min a max inclusive, XOR esse valor com X e armazena o resultado em X.
  • Agora XOR cada inteiro na matriz com X, armazenando cada resultado sucessivo em X como antes.
  • Quando estiver pronto, X será o valor do seu "buraco".

Isso será executado aproximadamente no tempo de 2N, semelhante à solução de bitvector, mas requer menos espaço de memória para qualquer N > sizeof (int). No entanto, se a matriz tiver múltiplos "orifícios", X será a "soma" XOR de todos os orifícios, o que será difícil ou impossível de separar nos valores reais dos orifícios. Nesse caso, você recorre a algum outro método, como o "pivot" ou o "bitvector", que se aproxima de outras respostas.

Você poderia reciclar isso também usando algo semelhante ao método de pivô para reduzir ainda mais a complexidade. Reorganize a matriz com base em um ponto de giro (que será o máximo do lado esquerdo e o mínimo da direita; será trivial encontrar o máximo e o mínimo do array completo ao girar). Se o lado esquerdo do pivô tiver um ou mais orifícios, recorra apenas a esse lado; caso contrário, recorrer para o outro lado. Em qualquer ponto onde você pode determinar que há apenas um buraco, use o método XOR para encontrá-lo (o que deve ser mais barato do que continuar girando até uma coleção de dois elementos com um furo conhecido, que é a base para o algoritmo de pivô puro).

    
por 24.04.2012 / 19:25
fonte
2

Qual é o intervalo de números que você encontrará? Se esse intervalo não for muito grande, você poderia resolver isso com duas varreduras (tempo linear O (n)) usando uma matriz com tantos elementos quanto números, trocando espaço por tempo. Você pode encontrar o intervalo dinamicamente com mais uma varredura. Para reduzir o espaço, você pode atribuir 1 bit a cada número, fornecendo 8 números de armazenamento por byte.

Sua outra opção, que pode ser melhor para cenários iniciais e seria insitu em vez de copiar a memória, é modificar a classificação de seleção para encerrar antecipadamente se a min. encontrada em uma passagem de verificação não for maior do que a última min. >     

por 24.04.2012 / 18:41
fonte
1

Não, não realmente. Como qualquer número ainda não escaneado sempre pode ser um que preencha um determinado "buraco", você não pode evitar escanear cada número pelo menos uma vez e depois compará-lo com os possíveis vizinhos. Você provavelmente poderia acelerar as coisas construindo uma árvore binária ou algo assim e, em seguida, percorrendo-a da esquerda para a direita até encontrar um buraco, mas isso é essencialmente da mesma complexidade que a classificação, já que ela está sendo classificada. E você provavelmente não vai aparecer com nada mais rápido do que o Timsort .

    
por 24.04.2012 / 18:52
fonte
1

A maioria das ideias aqui não é mais do que apenas ordenar. A versão do bitvector é o simples Bucketsort. A sorte também foi mencionada. Basicamente, resume-se a escolher o algoritmo de ordenação correto, que depende dos requisitos de tempo / espaço e também do intervalo e do número de elementos.

Na minha opinião, usar uma estrutura de heap é provavelmente a solução mais geral (uma pilha basicamente fornece os menores elementos de maneira eficiente sem uma classificação completa).

Você também pode analisar abordagens que localizam os números menores primeiro e, em seguida, examinam cada número inteiro maior do que isso. Ou você encontra os 5 números menores esperando que haja uma lacuna.

Todos esses algoritmos têm sua força dependendo das características de entrada e dos requisitos do programa.

    
por 26.04.2012 / 09:40
fonte
0

Uma solução que não usa armazenamento adicional ou assume a largura (32 bits) de inteiros.

  1. Em um passe linear, encontre o menor número. Vamos chamar isso de "min". O (n) complexidade do tempo.

  2. Escolha um elemento dinâmico aleatório e faça uma partição de estilo quicksort.

  3. Se o pivô acabou na posição = ("pivot" - "min"), então recurse no lado direito da partição, caso contrário, recurse no lado esquerdo da partição. A ideia aqui é que, se não houver buracos desde o início, o pivô estaria na posição "pivot" - "min"), então o primeiro buraco deve estar à direita da partição e vice-versa.

  4. O caso base é uma matriz de 1 elemento e o buraco está entre esse elemento e o próximo.

A complexidade total esperada do tempo de execução é O (n) (8 * n com as constantes) e o pior caso é O (n ^ 2). A análise de complexidade de tempo para um problema semelhante pode ser encontrada aqui .

    
por 25.04.2012 / 17:39
fonte
0

Acredito que crie algo que funcione de maneira geral e eficiente se você não tiver duplicatas * (no entanto, ele deve ser extensível a qualquer número de falhas e a qualquer intervalo de inteiros).

A idéia por trás desse método é como quicksort, em que encontramos um pivô e uma partição ao redor dele, depois reconsideramos o (s) lado (s) com um buraco. Para ver quais lados têm o buraco, encontramos os números mais baixos e mais altos e os comparamos com o pivô e o número de valores daquele lado. Digamos que o pivô seja 17 e o número mínimo seja 11. Se não houver furos, deve haver 6 números (11, 12, 13, 14, 15, 16, 17). Se houver 5, sabemos que há um buraco nesse lado e podemos recorrer apenas àquele lado para encontrá-lo. Estou tendo problemas em explicar isso mais claramente do que isso, então vamos dar um exemplo.

15 21 10 13 18 16 22 23 24 20 17 11 25 12 14

Pivô:

10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25

15 é o pivô, indicado por tubos ( || ). Existem 5 números no lado esquerdo do pivô, como deveria haver (15 - 10), e 9 no lado direito, onde deveria haver 10 (25 - 15). Então recapitamos no lado direito; Notaremos que o limite anterior era 15, caso o buraco estivesse adjacente a ele (16).

[15] 18 16 17 20 |21| 22 23 24 25

Agora, há 4 números no lado esquerdo, mas deve haver 5 (21 - 16). Então, nós recapitulamos lá, e novamente notamos o limite anterior (entre parênteses).

[15] 16 17 |18| 20 [21]

O lado esquerdo tem os 2 números corretos (18 - 16), mas o direito tem 1 em vez de 2 (20 - 18). Dependendo de nossas condições finais, poderíamos comparar o número 1 com os dois lados (18, 20) e ver que 19 está faltando ou recorrer mais uma vez:

[18] |20| [21]

O lado esquerdo tem um tamanho de zero, com uma lacuna entre o pivô (20) e o limite anterior (18), então 19 é o buraco.

*: Se houver duplicatas, você provavelmente poderia usar um hash para removê-las no tempo O (N), mantendo o método geral O (N), mas isso poderia demorar mais tempo do que usando algum outro método.

    
por 25.04.2012 / 16:35
fonte