Início / coding / Perguntas / 79557159
Accepted
Utsav
Asked: 2025-04-05 23:18:09 +0800 CST

Retorna o primeiro inteiro positivo ausente

  • 772

Há uma lista de inteiros com valores positivos e negativos. Precisamos retornar o primeiro inteiro positivo ausente.

Por exemplo.

  1. Entrada - 3 -1 1 0 4 , Saída Esperada - 2
  2. Entrada - -1 -4 -3, Saída Esperada - 1
  3. Entrada - 1 3 2, Saída esperada - 4

Eu poderia chegar à solução abaixo que pode ter muito escopo para otimização. Só queria verificar se poderia haver uma solução O(n) que não usasse lógica de classificação. Se não, então alguma outra solução otimizada abaixo.

q)f: {if[all x<1;:1]; x: asc x where x>0;  b:1+first where not x=1+til count x; $[0N=b;1+last x;b]}
q)f -1 -4 -3
1
q)f 1 3 2
4
q)f 3 -1 1 0 4
2
kdb+

2 respostas

  1. Lógica semelhante à resposta de Cathal, mas usando exceptno lugar de c where not c in xe descartando as verificações de condição:

    q)f:{(1+max x)^first(1+til count x)except x}
q)f -1 -4 -3
1
q)f 1 3 2
4
q)f 3 -1 1 0 4
2

    A desvantagem é que ele é mais lento nos casos com todas as entradas <0 (pois não aborta antes do tempo), mas é mais rápido para casos com entradas com uma entrada >1.

    • 2
  2. Best Answer
    q)f:{$[all x<1;1;$[null o:first c where not(c:1+til count x)in x;1+max x;o]]}
q)f -1 -4 -3
1
q)f 1 3 2
4
q)f 3 -1 1 0 4
2
    • 1

relate perguntas