Algoritmo para determinar se o array contém n… n + m?

Eu vi esta pergunta no Reddit, e não houve soluções positivas apresentadas, e eu pensei que seria uma pergunta perfeita para perguntar aqui. Esta foi uma discussão sobre perguntas da entrevista:

Escreva um método que tome uma matriz int de tamanho m e retorne (Verdadeiro / Falso) se a matriz consistir dos números n … n + m-1, todos os números nessa faixa e apenas números nessa faixa. A matriz não é garantida para ser classificada. (Por exemplo, {2,3,4} retornaria verdadeiro. {1,3,1} retornaria falso, {1,2,4} retornaria falso.

O problema que tive com este aqui é que meu entrevistador me pediu para otimizar (mais rápido O (n), menos memory, etc), ao ponto de ele alegar que você poderia fazê-lo em uma passagem da matriz usando uma quantidade constante de memory. Nunca percebi isso.

Juntamente com suas soluções, indique se elas assumem que a matriz contém itens exclusivos. Indique também se a sua solução assume que a sequência começa em 1. (modifiquei a questão ligeiramente para permitir que os casos passem em 2, 3, 4 …)

edit: Eu sou agora da opinião de que não existe um algoritmo linear no tempo e constante no espaço que lida com duplicatas. Alguém pode verificar isso?

O problema duplicado resume-se a testar para ver se o array contém duplicados em tempo O (n), espaço O (1). Se isso puder ser feito, você pode simplesmente testar primeiro e, se não houver duplicatas, executar os algoritmos postados. Então você pode testar dupes no espaço O (n) time O (1)?

    Sob a hipótese de que números menores que um não são permitidos e não há duplicatas, há uma identidade de sum simples para isso – a sum dos números de 1 a m em incrementos de 1 é (m * (m + 1)) / 2 . Você pode então sumr o array e usar essa identidade.

    Você pode descobrir se há um dupe sob as garantias acima, mais a garantia nenhum número é acima de m ou menor que n (que pode ser verificado em O(N) )

    A ideia no pseudo-código:
    0) Comece em N = 0
    1) Pegue o N-ésimo elemento na lista.
    2) Se não estiver no lugar certo se a lista foi classificada, verifique onde ela deveria estar.
    3) Se o lugar onde deveria estar já tem o mesmo número, você tem um dupe – RETURN TRUE
    4) Caso contrário, troque os números (para colocar o primeiro número no lugar certo).
    5) Com o número que você acabou de trocar, ele está no lugar certo?
    6) Se não, volte para o passo dois.
    7) Caso contrário, inicie na etapa um com N = N + 1. Se isso estiver além do final da lista, você não terá enganos.

    E, sim, isso é executado em O(N) embora possa parecer com O(N ^ 2)

    Nota para todos (coisas coletadas de comentários)

    Essa solução funciona sob a suposição de que você pode modificar a matriz e, em seguida, usa a sorting Radix no local (que atinge a velocidade O(N) ).

    Outras soluções matemáticas foram apresentadas, mas não tenho certeza de que nenhuma delas tenha sido provada. Há um monte de sums que podem ser úteis, mas a maioria delas gera uma explosão no número de bits necessários para representar a sum, o que violará a garantia constante de espaço extra. Eu também não sei se algum deles é capaz de produzir um número distinto para um dado conjunto de números. Eu acho que uma sum de quadrados pode funcionar, que tem uma fórmula conhecida para calculá-lo (ver Wolfram )

    Novo insight (bem, mais reflexões que não ajudam a resolvê-lo, mas são interessantes e vou dormir):

    Então, foi mencionado para talvez usar sum + sum de quadrados. Ninguém sabia se isso funcionava ou não, e percebi que só se torna um problema quando (x + y) = (n + m), como o fato de 2 + 2 = 1 + 3. As praças também têm esse problema graças a Triplas pitagóricos (então 3 ^ 2 + 4 ^ 2 + 25 ^ 2 == 5 ^ 2 + 7 ^ 2 + 24 ^ 2, e a sum dos quadrados não funciona). Se usarmos o último teorema de Fermat , sabemos que isso não pode acontecer com n ^ 3. Mas também não sabemos se não há x + y + z = n para isso (a menos que o façamos e eu não saiba). Portanto, não há garantia de que isso também não se rompa – e se continuarmos nesse caminho, rapidamente ficamos sem bits.

    Na minha alegria, no entanto, esqueci de notar que você pode quebrar a sum dos quadrados, mas ao fazer isso você cria uma sum normal que não é válida. Eu não acho que você pode fazer as duas coisas, mas, como já foi notado, nós não temos nenhuma prova.


    Devo dizer que encontrar contra-exemplos é, às vezes, muito mais fácil do que provar as coisas! Considere as seguintes seqüências, todas com sum de 28 e sum de quadrados de 140:

     [1, 2, 3, 4, 5, 6, 7] [1, 1, 4, 5, 5, 6, 6] [2, 2, 3, 3, 4, 7, 7] 

    Eu não consegui encontrar nenhum desses exemplos de tamanho 6 ou menor. Se você quiser um exemplo que tenha os valores min e max apropriados, tente este de tamanho 8:

     [1, 3, 3, 4, 4, 5, 8, 8] 

    Abordagem mais simples (modificando a ideia de hazzen):

    Um array inteiro de comprimento m contém todos os números de n para n + m-1 exatamente uma vez se

    • cada elemento da matriz é entre n e n + m-1
    • não há duplicatas

    (Motivo: existem apenas m valores no intervalo inteiro dado, portanto, se a matriz contiver valores únicos neste intervalo, ele deverá conter cada um deles uma vez)

    Se você tem permissão para modificar o array, você pode verificar ambos em uma passagem através da lista com uma versão modificada da idéia do algoritmo de hazzen (não há necessidade de fazer nenhum sumtório):

    • Para todos os índices de array i de 0 a m-1
      1. Se array [i] = n + m => RETURN FALSE (“valor fora do intervalo encontrado”)
      2. Calcule j = array [i] – n (esta é a posição baseada em 0 da matriz [i] em uma matriz ordenada com valores de n a n + m-1)
      3. Enquanto j não é igual a i
        1. Se list [i] é igual a listar [j] => RETURN FALSE (“duplicado encontrado”)
        2. Trocar lista [i] com lista [j]
        3. Recalcular j = matriz [i] – n
    • RETURN TRUE

    Não tenho certeza se a modificação da matriz original conta contra o espaço adicional máximo permitido de O (1), mas se não for essa deve ser a solução que o pôster original queria.

    Trabalhando com a[i] % a.length vez de a[i] reduz-se o problema de determinar que você tem os números 0 a a.length - 1 .

    Nós tomamos esta observação como certa e tentamos verificar se a matriz contém [0, m).

    Encontre o primeiro nó que não está em sua posição correta, por exemplo

     0 1 2 3 7 5 6 8 4 ; the original dataset (after the renaming we discussed) ^ `---this is position 4 and the 7 shouldn't be here 

    Troque esse número para onde deveria estar. ou seja, troque o 7 pelo 8 :

     0 1 2 3 8 5 6 7 4 ; | `--------- 7 is in the right place. `--------------- this is now the 'current' position 

    Agora nós repetimos isso. Olhando novamente para a nossa posição atual, pedimos:

    “este é o número correto para aqui?”

    • Se não, nós o trocamos em seu lugar correto.
    • Se estiver no lugar certo, nos movemos para a direita e fazemos isso novamente.

    Seguindo essa regra novamente, obtemos:

     0 1 2 3 4 5 6 7 8 ; 4 and 8 were just swapped 

    Isso irá gradualmente construir a lista corretamente da esquerda para a direita, e cada número será movido no máximo uma vez e, portanto, este é O (n).

    Se houver dupes, notamos que logo há uma tentativa de trocar um número de backwards para backwards na lista.

    Por que as outras soluções usam um sumtório de todos os valores? Eu acho que isso é arriscado, porque quando você sum O (n) itens em um número, você está tecnicamente usando mais de O (1) espaço.

    Método mais simples:

    Etapa 1, descubra se há alguma duplicata. Não tenho certeza se isso é possível no espaço O (1). De qualquer forma, retorne false se houver duplicatas.

    Etapa 2, percorra a lista, acompanhe os itens mais baixos e mais altos .

    Passo 3, faz (maior – menor) igual m? Se sim, retorne verdadeiro.

    Qualquer algoritmo de uma passagem requer Omega (n) bits de armazenamento.

    Suponha, ao contrário, que exista um algoritmo de uma passagem que use o (n) bits. Como ele faz apenas uma passagem, ele deve resumir os primeiros valores de n / 2 em o (n) espaço. Como existem C (n, n / 2) = 2 ^ Theta (n) possíveis conjuntos de n / 2 valores extraídos de S = {1, …, n}, existem dois conjuntos distintos A e B de n / 2 valores tais que o estado da memory é o mesmo depois de ambos. Se A ‘= S \ A é o conjunto de valores “correto” para complementar A, então o algoritmo não pode responder corretamente para as inputs

    AA ‘- sim

    BA ‘- não

    já que não consegue distinguir o primeiro caso do segundo.

    QED

    Votem-me se estiver errado, mas acho que podemos determinar se há duplicatas ou não usando variância. Como sabemos a média de antemão (n + (m-1) / 2 ou algo assim), podemos sumr os números e o quadrado da diferença para ver se a sum corresponde à equação (mn + m (m-1) ) / 2) e a variância é (0 + 1 + 4 + … + (m-1) ^ 2) / m. Se a variação não corresponder, é provável que tenhamos uma duplicata.

    EDIT: variação é suposto ser (0 + 1 + 4 + … + [(m-1) / 2] ^ 2) * 2 / m, porque metade dos elementos são menores que a média e a outra metade é maior que a média.

    Se houver uma duplicata, um termo na equação acima será diferente da sequência correta, mesmo que outra duplicata anule completamente a alteração na média. Portanto, a function retorna true somente se sum e variância corresponderem aos valores desejados, que podemos calcular antecipadamente.

    Aqui está uma solução de trabalho em O (n)

    Isso está usando o pseudocódigo sugerido por Hazzen e algumas das minhas próprias idéias. Ele funciona também para números negativos e não requer nenhuma sum de quadrados.

     function testArray($nums, $n, $m) { // check the sum. PHP offers this array_sum() method, but it's // trivial to write your own. O(n) here. if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) { return false; // checksum failed. } for ($i = 0; $i < $m; ++$i) { // check if the number is in the proper range if ($nums[$i] < $n || $nums[$i] >= $n + $m) { return false; // value out of range. } while (($shouldBe = $nums[$i] - $n) != $i) { if ($nums[$shouldBe] == $nums[$i]) { return false; // duplicate } $temp = $nums[$i]; $nums[$i] = $nums[$shouldBe]; $nums[$shouldBe] = $temp; } } return true; // huzzah! } var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5)); // true var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5)); // true var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5)); // false - out of range var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5)); // false - checksum fail var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5)); // false - dupe var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true 

    Algum tempo atrás, ouvi falar de um algoritmo de seleção muito inteligente de alguém que trabalhava para a companhia telefônica. Eles tiveram que classificar um número enorme de números de telefone. Depois de passar por um monte de estratégias de sorting diferentes, eles finalmente chegaram a uma solução muito elegante: eles apenas criaram uma matriz de bits e trataram o deslocamento na matriz de bits como o número de telefone. Eles então varreram seu database com um único passo, mudando o bit para cada número para 1. Depois disso, eles passaram pelo array de bits uma vez, cuspindo os números de telefone para as inputs que tinham o bit definido alto.

    Nesse sentido, acredito que você possa usar os dados no próprio array como uma estrutura de metadados para procurar duplicatas. Na pior das hipóteses, você poderia ter uma matriz separada, mas eu tenho certeza que você pode usar a matriz de input se você não se importa um pouco de troca.

    Vou deixar de fora o parâmetro n por enquanto, b / c que apenas confunde as coisas – adicionar em um deslocamento de índice é bem fácil de fazer.

    Considerar:

     for i = 0 to m if (a[a[i]]==a[i]) return false; // we have a duplicate while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i) sum = sum + a[i] next if sum = (n+m-1)*m return true else return false 

    Este não é O (n) – provavelmente mais próximo de O (n Log n) – mas fornece espaço constante e pode fornecer um vetor diferente de ataque para o problema.

    Se quisermos O (n), então usar uma matriz de bytes e algumas operações de bits fornecerá a verificação de duplicação com um n / 32 bytes extra de memory usada (assumindo 32 bits, é claro).

    EDIT: O algoritmo acima poderia ser melhorado adicionando a verificação de sum para o interior do loop e verifique:

     if sum > (n+m-1)*m return false 

    Dessa forma, irá falhar rapidamente.

    Supondo que você saiba apenas o comprimento da matriz e você tem permissão para modificar a matriz, isso pode ser feito no espaço O (1) e na hora O (n).

    O processo tem dois passos diretos. 1. “modulo sort” o array. [5,3,2,4] => [4,5,2,3] (O (2n)) 2. Verifique se o vizinho de cada valor é um mais alto que ele mesmo (módulo) (O (n))

    Todos disseram que você precisa no máximo de 3 passes através da matriz.

    O modulo sort é a parte ‘complicada’, mas o objective é simples. Pegue cada valor na matriz e armazene-o em seu próprio endereço (comprimento do módulo). Isso requer uma passagem pela matriz, fazendo o loop de cada local ‘desviando’ seu valor, trocando-o para seu local correto e movendo o valor em seu destino. Se você alguma vez mover um valor que seja congruente com o valor que você acabou de despejar, você terá uma duplicata e poderá sair mais cedo. No pior dos casos, é O (2n).

    A verificação é uma única passagem pela matriz, examinando cada valor com seu próximo vizinho mais alto. Sempre).

    O algoritmo combinado é O (n) + O (2n) = O (3n) = O (n)

    Pseudocódigo da minha solução:

     foreach (valores []) 
       while (valores [i] não congruentes para i)
         a ser expulso = valores [i]
         evict (valores [i]) // troca para sua localização 'correta'
         if (valores [i]% length == a ser despejado% length)
           retorna falso;  // um 'duplicado' chegou quando despejamos esse número
       terminar enquanto
     fim foreach
     foreach (valores [])
       if ((valores [i] +1)% length! = valores [i + 1]% length)
         retorna falso
     fim foreach
    

    Eu incluí a prova de conceito do código Java abaixo, não é bonita, mas ela passa em todos os testes de unidade que fiz para ela. Eu chamo isso de ‘StraightArray’ porque eles correspondem à mão de poker de um straight (sequenciamento contíguo que ignora o naipe).

     public class StraightArray { static int evict(int[] a, int i) { int t = a[i]; a[i] = a[t%a.length]; a[t%a.length] = t; return t; } static boolean isStraight(int[] values) { for(int i = 0; i < values.length; i++) { while(values[i]%values.length != i) { int evicted = evict(values, i); if(evicted%values.length == values[i]%values.length) { return false; } } } for(int i = 0; i < values.length-1; i++) { int n = (values[i]%values.length)+1; int m = values[(i+1)]%values.length; if(n != m) { return false; } } return true; } } 

    Implementação do algoritmo de Hazzen em C

     #include #define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j]; int check_ntom(int a[], int n, int m) { int i = 0, j = 0; for(i = 0; i < m; i++) { if(a[i] < n || a[i] >= n+m) return 0; //invalid entry j = a[i] - n; while(j != i) { if(a[i]==a[j]) return -1; //bucket already occupied. Dupe. swapxor(a, i, j); //faster bitwise swap j = a[i] - n; if(a[i]>=n+m) return 0; //[NEW] invalid entry } } return 200; //OK } int main() { int n=5, m=5; int a[] = {6, 5, 7, 9, 8}; int r = check_ntom(a, n, m); printf("%d", r); return 0; } 

    Editar: alteração feita no código para eliminar o access à memory ilegal.

     boolean determineContinuousArray(int *arr, int len) { // Suppose the array is like below: //int arr[10] = {7,11,14,9,8,100,12,5,13,6}; //int len = sizeof(arr)/sizeof(int); int n = arr[0]; int *result = new int[len]; for(int i=0; i< len; i++) result[i] = -1; for (int i=0; i < len; i++) { int cur = arr[i]; int hold ; if ( arr[i] < n){ n = arr[i]; } while(true){ if ( cur - n >= len){ cout << "array index out of range: meaning this is not a valid array" << endl; return false; } else if ( result[cur - n] != cur){ hold = result[cur - n]; result[cur - n] = cur; if (hold == -1) break; cur = hold; }else{ cout << "found duplicate number " << cur << endl; return false; } } } cout << "this is a valid array" << endl; for(int j=0 ; j< len; j++) cout << result[j] << "," ; cout << endl; return true; } 
     def test(a, n, m): seen = [False] * m for x in a: if x < n or x >= n+m: return False if seen[xn]: return False seen[xn] = True return False not in seen print test([2, 3, 1], 1, 3) print test([1, 3, 1], 1, 3) print test([1, 2, 4], 1, 3) 

    Note que isto apenas faz uma passagem através da primeira matriz, não considerando a busca linear envolvida em not in . 🙂

    Eu também poderia ter usado um set python, mas optei pela solução direta em que as características de desempenho do set não precisam ser consideradas.

    Atualização: Smashery apontou que eu tinha errado uma “quantidade constante de memory” e esta solução não resolve o problema.

    Se você quiser saber a sum dos números [n ... n + m - 1] basta usar esta equação.

     var sum = m * (m + 2 * n - 1) / 2; 

    Isso funciona para qualquer número, positivo ou negativo, mesmo que n seja um decimal.

    Por que as outras soluções usam um sumtório de todos os valores? Eu acho que isso é arriscado, porque quando você sum O (n) itens em um número, você está tecnicamente usando mais de O (1) espaço.

    O (1) indica um espaço constante que não é alterado pelo número de n. Não importa se é 1 ou 2 variables, desde que seja um número constante. Por que você está dizendo que é mais do que O (1) espaço? Se você está calculando a sum de n números, acumulando-o em uma variável temporária, você estaria usando exatamente uma variável de qualquer maneira.

    Comentando em uma resposta porque o sistema não me permite escrever comentários ainda.

    Atualização (em resposta a comentários): nesta resposta eu quis dizer O (1) espaço onde “espaço” ou “tempo” foi omitido. O texto citado faz parte de uma resposta anterior à qual esta é uma resposta.

    Dado isto –

    Escreva um método que tenha uma matriz int de tamanho m …

    Eu suponho que é justo concluir que há um limite superior para m, igual ao valor do maior int (sendo tipicamente 2 ^ 32). Em outras palavras, mesmo que m não seja especificado como um int, o fato de que o array não pode ter duplicatas implica que não pode haver mais do que o número de valores que você pode formar a partir de 32 bits, o que implica m limitado a ser um int também.

    Se tal conclusão for aceitável, então proponho usar um espaço fixo de (2 ^ 33 + 2) * 4 bytes = 34,359,738,376 bytes = 34,4 GB para lidar com todos os casos possíveis. (Sem contar o espaço requerido pela matriz de input e seu loop).

    É claro que, para otimização, eu primeiro levaria em conta e alocaria apenas a quantidade real necessária, (2m + 2) * 4 bytes.

    Se isso for aceitável para a restrição de espaço O (1) – para o problema declarado – então deixe-me prosseguir para uma proposta algorítmica … 🙂

    Suposições : matriz de m ints, positiva ou negativa, nenhuma maior do que 4 bytes podem conter. Duplicatas são tratadas. Primeiro valor pode ser qualquer int válido. Restringir m como acima.

    Primeiro , crie um array int de comprimento 2m-1, ary e forneça três variables ​​int: left , diff e right . Observe que faz 2m + 2 …

    Segundo , pegue o primeiro valor da matriz de input e copie-o para a posição m-1 na nova matriz. Inicialize as três variables.

    • definir ary [m-1] – nthVal // n = 0
    • defina para a esquerda = diff = right = 0

    Terceiro , percorra os valores restantes na matriz de input e faça o seguinte para cada iteração:

    • conjunto diff = nthVal – ary [m-1]
    • if ( diff > m-1 + direita || diff <1-m + left ) retorna falso // fora dos limites
    • if ( ary [m-1 + diff ]! = null) retorna falso // duplicado
    • definir ary [m-1 + diff ] = nthVal
    • if ( diff > left ) left = diff // constrange o limite esquerdo mais à direita
    • if ( diff < right ) right = diff // restringe a direita para a esquerda

    Eu decidi colocar isso no código e funcionou.

    Aqui está uma amostra de trabalho usando C #:

     public class Program { static bool puzzle(int[] inAry) { var m = inAry.Count(); var outAry = new int?[2 * m - 1]; int diff = 0; int left = 0; int right = 0; outAry[m - 1] = inAry[0]; for (var i = 1; i < m; i += 1) { diff = inAry[i] - inAry[0]; if (diff > m - 1 + right || diff < 1 - m + left) return false; if (outAry[m - 1 + diff] != null) return false; outAry[m - 1 + diff] = inAry[i]; if (diff > left) left = diff; if (diff < right) right = diff; } return true; } static void Main(string[] args) { var inAry = new int[3]{ 2, 3, 4 }; Console.WriteLine(puzzle(inAry)); inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 }; Console.WriteLine(puzzle(inAry)); inAry = new int[3] { 21, 31, 41 }; Console.WriteLine(puzzle(inAry)); Console.ReadLine(); } } 

    nota : este comentário é baseado no texto original da questão (foi corrigido desde então)

    Se a questão é colocada exatamente como está escrito acima (e não é apenas um erro de digitação) e para uma matriz de tamanho n a function deve retornar (True / False) se a matriz consistir dos números 1 … n + 1,

    … então a resposta será sempre falsa porque o array com todos os números 1 … n + 1 será do tamanho n + 1 e não n. daí a questão pode ser respondida em O (1). 🙂

    Exemplo de contador para o algoritmo XOR .

    (não pode postar como comentário)

    @opopome

    Para a = {0, 2, 7, 5,} ele retorna true (significa que a é uma permutação do intervalo [0, 4) ), mas deve retornar false neste caso ( a é obviamente não é uma permutação de [0, 4) ).

    Outro exemplo de contador: {0, 0, 1, 3, 5, 6, 6} – todos os valores estão no intervalo, mas há duplicatas.

    Eu poderia implementar incorretamente a idéia do popopome (ou testes), portanto aqui está o código:

     bool isperm_popopome(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, no restrictions on n, no overflow, a[] may be readonly */ int even_xor = 0; int odd_xor = 0; for (int i = 0; i < m; ++i) { if (a[i] % 2 == 0) // is even even_xor ^= a[i]; else odd_xor ^= a[i]; const int b = i + n; if (b % 2 == 0) // is even even_xor ^= b; else odd_xor ^= b; } return (even_xor == 0) && (odd_xor == 0); } 

    Versão AC do pseudocódigo do b3

    (para evitar erros de interpretação do pseudocódigo)

    Exemplo de contador: {1, 1, 2, 4, 6, 7, 7} .

     int pow_minus_one(int power) { return (power % 2 == 0) ? 1 : -1; } int ceil_half(int n) { return n / 2 + (n % 2); } bool isperm_b3_3(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, doesn't use n possible overflow in sum a[] may be readonly */ int altsum = 0; int mina = INT_MAX; int maxa = INT_MIN; for (int i = 0; i < m; ++i) { const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0 if (mina > v) mina = v; if (maxa < v) maxa = v; altsum += pow_minus_one(v) * v; } return ((maxa-mina == m-1) and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1) - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum)); } 

    Em Python:

     def ispermutation(iterable, m, n): """Whether iterable and the range [n, n+m) have the same elements. pre-condition: there are no duplicates in the iterable """ for i, elem in enumerate(iterable): if not n <= elem < n+m: return False return i == m-1 print(ispermutation([1, 42], 2, 1) == False) print(ispermutation(range(10), 10, 0) == True) print(ispermutation((2, 1, 3), 3, 1) == True) print(ispermutation((2, 1, 3), 3, 0) == False) print(ispermutation((2, 1, 3), 4, 1) == False) print(ispermutation((2, 1, 3), 2, 1) == False) 

    É O (m) no tempo e O (1) no espaço. Não leva em conta duplicatas.

    Solução alternativa:

     def ispermutation(iterable, m, n): """Same as above. pre-condition: assert(len(list(iterable)) == m) """ return all(n <= elem < n+m for elem in iterable) 

    MINHA MELHOR OPÇÃO ATUAL

     def uniqueSet( array ) check_index = 0; check_value = 0; min = array[0]; array.each_with_index{ |value,index| check_index = check_index ^ ( 1 << index ); check_value = check_value ^ ( 1 << value ); min = value if value < min } check_index = check_index << min; return check_index == check_value; end 

    O (n) e Espaço O (1)

    Eu escrevi um script para combinações de força bruta que poderiam falhar e não encontrei nenhuma. Se você tem uma matriz que contraria esta function, diga. 🙂


    @JF Sebastian

    Não é um verdadeiro algoritmo hash. Tecnicamente, é uma matriz booleana altamente eficiente de valores "vistos".

     ci = 0, cv = 0 [5,4,3]{ i = 0 v = 5 1 << 0 == 000001 1 << 5 == 100000 0 ^ 000001 = 000001 0 ^ 100000 = 100000 i = 1 v = 4 1 << 1 == 000010 1 << 4 == 010000 000001 ^ 000010 = 000011 100000 ^ 010000 = 110000 i = 2 v = 3 1 << 2 == 000100 1 << 3 == 001000 000011 ^ 000100 = 000111 110000 ^ 001000 = 111000 } min = 3 000111 << 3 == 111000 111000 === 111000 

    O ponto principal é que, para "falsificar" a maioria dos casos de problemas, são usados ​​duplicados para fazer isso. Neste sistema, o XOR penaliza você por usar o mesmo valor duas vezes e assume que você o fez 0 vezes.

    As advertências aqui são, é claro:

    1. o comprimento da matriz de input e o valor máximo da matriz são limitados pelo valor máximo de $x em ( 1 << $x > 0 )
    2. a eficácia final depende de como o seu sistema subjacente implementa as habilidades para:

      1. Deslocar 1 bit n coloca à direita.
      2. xor 2 registros. (onde 'registros' podem, dependendo da implementação, abranger vários registros)

      editar Observado, as declarações acima parecem confusas. Assuming a perfect machine, where an "integer" is a register with Infinite precision, which can still perform a ^ b in O(1) time.

    But failing these assumptions, one has to start asking the algorithmic complexity of simple math.

    • How complex is 1 == 1 ?, surely that should be O(1) every time right?.
    • What about 2^32 == 2^32 .
    • O(1)? 2^33 == 2^33? Now you've got a question of register size and the underlying implementation.
    • Fortunately XOR and == can be done in parallel, so if one assumes infinite precision and a machine designed to cope with infinite precision, it is safe to assume XOR and == take constant time regardless of their value ( because its infinite width, it will have infinite 0 padding. Obviously this doesn't exist. But also, changing 000000 to 000100 is not increasing memory usage.
    • Yet on some machines , ( 1 << 32 ) << 1 will consume more memory, but how much is uncertain.

    AC version of Kent Fredric’s Ruby solution

    (to facilitate testing)

    Counter-example (for C version): {8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5, 18, 12, 2, 9, 14, 17, 21, 19, 22, 15, 20, 24, 11, 10, 16, 25}. Here n=0, m=35. This sequence misses 34 and has two 2 .

    It is an O(m) in time and O(1) in space solution.

    Out-of-range values are easily detected in O(n) in time and O(1) in space, therefore tests are concentrated on in-range (means all values are in the valid range [n, n+m) ) sequences. Otherwise {1, 34} is a counter example (for C version, sizeof(int)==4, standard binary representation of numbers).

    The main difference between C and Ruby version: << operator will rotate values in C due to a finite sizeof(int), but in Ruby numbers will grow to accomodate the result eg,

    Ruby: 1 << 100 # -> 1267650600228229401496703205376

    C: int n = 100; 1 << n // -> 16

    In Ruby: check_index ^= 1 << i; is equivalent to check_index.setbit(i) . The same effect could be implemented in C++: vector v(m); v[i] = true;

     bool isperm_fredric(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, no restriction on n, ?overflow? a[] may be readonly */ int check_index = 0; int check_value = 0; int min = a[0]; for (int i = 0; i < m; ++i) { check_index ^= 1 << i; check_value ^= 1 << (a[i] - n); // if (a[i] < min) min = a[i]; } check_index <<= min - n; // min and n may differ eg, // {1, 1}: min=1, but n may be 0. return check_index == check_value; } 

    Values of the above function were tested against the following code:

     bool *seen_isperm_trusted = NULL; bool isperm_trusted(int m; int a[m], int m, int n) { /** O(m) in time, O(m) in space */ for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t)); seen_isperm_trusted[i] = false; for (int i = 0; i < m; ++i) { if (a[i] < n or a[i] >= n + m) return false; // out of range if (seen_isperm_trusted[a[i]-n]) return false; // duplicates else seen_isperm_trusted[a[i]-n] = true; } return true; // a[] is a permutation of the range: [n, n+m) } 

    Input arrays are generated with:

     void backtrack(int m; int a[m], int m, int nitems) { /** generate all permutations with repetition for the range [0, m) */ if (nitems == m) { (void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1} } else for (int i = 0; i < m; ++i) { a[nitems] = i; backtrack(a, m, nitems + 1); } } 

    The Answer from “nickf” dows not work if the array is unsorted var_dump(testArray(array(5, 3, 1, 2, 4), 1, 5)); //gives “duplicates” !!!!

    Also your formula to compute sum([n…n+m-1]) looks incorrect…. the correct formula is (m(m+1)/2 – n(n-1)/2)

    An array contains N numbers, and you want to determine whether two of the numbers sum to a given number K. For instance, if the input is 8,4, 1,6 and K is 10, the answer is yes (4 and 6). A number may be used twice. Do the following. uma. Give an O(N2) algorithm to solve this problem. b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items first. After doing so, you can solve the problem in linear time.) c. Code both solutions and compare the running times of your algorithms. 4

    Product of m consecutive numbers is divisible by m! [ m factorial ]


    so in one pass you can compute the product of the m numbers, also compute m! and see if the product modulo m ! is zero at the end of the pass

    I might be missing something but this is what comes to my mind …

    something like this in python

    my_list1 = [9,5,8,7,6]

    my_list2 = [3,5,4,7]

    def consecutive(my_list):

     count = 0 prod = fact = 1 for num in my_list: prod *= num count +=1 fact *= count if not prod % fact: return 1 else: return 0 

    print consecutive(my_list1)

    print consecutive(my_list2)


    HotPotato ~$ python m_consecutive.py

    1

    0

    I propose the following:

    Choose a finite set of prime numbers P_1,P_2,…,P_K, and compute the occurrences of the elements in the input sequence (minus the minimum) modulo each P_i. The pattern of a valid sequence is known.

    For example for a sequence of 17 elements, modulo 2 we must have the profile: [9 8], modulo 3: [6 6 5], modulo 5: [4 4 3 3 3], etc.

    Combining the test using several bases we obtain a more and more precise probabilistic test. Since the entries are bounded by the integer size, there exists a finite base providing an exact test. This is similar to probabilistic pseudo primality tests.

     S_i is an int array of size P_i, initially filled with 0, i=1..K M is the length of the input sequence Mn = INT_MAX Mx = INT_MIN for x in the input sequence: for i in 1..K: S_i[x % P_i]++ // count occurrences mod Pi Mn = min(Mn,x) // update min Mx = max(Mx,x) // and max if Mx-Mn != M-1: return False // Check bounds for i in 1..K: // Check profile mod P_i Q = M / P_i R = M % P_i Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1 if this test fails, return False return True 

    Any contiguous array [ n, n+1, …, n+m-1 ] can be mapped on to a ‘base’ interval [ 0, 1, …, m ] using the modulo operator. For each i in the interval, there is exactly one i%m in the base interval and vice versa.

    Any contiguous array also has a ‘span’ m (maximum – minimum + 1) equal to it’s size.

    Using these facts, you can create an “encountered” boolean array of same size containing all falses initially, and while visiting the input array, put their related “encountered” elements to true.

    This algorithm is O(n) in space, O(n) in time, and checks for duplicates.

     def contiguous( values ) #initialization encountered = Array.new( values.size, false ) min, max = nil, nil visited = 0 values.each do |v| index = v % encountered.size if( encountered[ index ] ) return "duplicates"; end encountered[ index ] = true min = v if min == nil or v < min max = v if max == nil or v > max visited += 1 end if ( max - min + 1 != values.size ) or visited != values.size return "hole" else return "contiguous" end end tests = [ [ false, [ 2,4,5,6 ] ], [ false, [ 10,11,13,14 ] ] , [ true , [ 20,21,22,23 ] ] , [ true , [ 19,20,21,22,23 ] ] , [ true , [ 20,21,22,23,24 ] ] , [ false, [ 20,21,22,23,24+5 ] ] , [ false, [ 2,2,3,4,5 ] ] ] tests.each do |t| result = contiguous( t[1] ) if( t[0] != ( result == "contiguous" ) ) puts "Failed Test : " + t[1].to_s + " returned " + result end end 

    I like Greg Hewgill’s idea of Radix sorting. To find duplicates, you can sort in O(N) time given the constraints on the values in this array.

    For an in-place O(1) space O(N) time that restores the original ordering of the list, you don’t have to do an actual swap on that number; you can just mark it with a flag:

     //Java: assumes all numbers in arr > 1 boolean checkArrayConsecutiveRange(int[] arr) { // find min/max int min = arr[0]; int max = arr[0] for (int i=1; i max ? arr[i] : max); } if (max-min != arr.length) return false; // flag and check boolean ret = true; for (int i=0; i 

    Storing the flags inside the given array is kind of cheating, and doesn't play well with parallelization. I'm still trying to think of a way to do it without touching the array in O(N) time and O(log N) space. Checking against the sum and against the sum of least squares (arr[i] - arr.length/2.0)^2 feels like it might work. The one defining characteristic we know about a 0...m array with no duplicates is that it's uniformly distributed; we should just check that.

    Now if only I could prove it.

    I'd like to note that the solution above involving factorial takes O(N) space to store the factorial itself. N! > 2^N, which takes N bytes to store.

    Opa! I got caught up in a duplicate question and did not see the already identical solutions here. And I thought I’d finally done something original! Here is a historical archive of when I was slightly more pleased:


    Well, I have no certainty if this algorithm satisfies all conditions. In fact, I haven’t even validated that it works beyond a couple test cases I have tried. Even if my algorithm does have problems, hopefully my approach sparks some solutions.

    This algorithm, to my knowledge, works in constant memory and scans the array three times. Perhaps an added bonus is that it works for the full range of integers, if that wasn’t part of the original problem.

    I am not much of a pseudo-code person, and I really think the code might simply make more sense than words. Here is an implementation I wrote in PHP. Take heed of the comments.

     function is_permutation($ints) { /* Gather some meta-data. These scans can be done simultaneously */ $lowest = min($ints); $length = count($ints); $max_index = $length - 1; $sort_run_count = 0; /* I do not have any proof that running this sort twice will always completely sort the array (of course only intentionally happening if the array is a permutation) */ while ($sort_run_count < 2) { for ($i = 0; $i < $length; ++$i) { $dest_index = $ints[$i] - $lowest; if ($i == $dest_index) { continue; } if ($dest_index > $max_index) { return false; } if ($ints[$i] == $ints[$dest_index]) { return false; } $temp = $ints[$dest_index]; $ints[$dest_index] = $ints[$i]; $ints[$i] = $temp; } ++$sort_run_count; } return true; } 

    So there is an algorithm that takes O(n^2) that does not require modifying the input array and takes constant space.

    First, assume that you know n and m . This is a linear operation, so it does not add any additional complexity. Next, assume there exists one element equal to n and one element equal to n+m-1 and all the rest are in [n, n+m) . Given that, we can reduce the problem to having an array with elements in [0, m) .

    Now, since we know that the elements are bounded by the size of the array, we can treat each element as a node with a single link to another element; in other words, the array describes a directed graph. In this directed graph, if there are no duplicate elements, every node belongs to a cycle, that is, a node is reachable from itself in m or less steps. If there is a duplicate element, then there exists one node that is not reachable from itself at all.

    So, to detect this, you walk the entire array from start to finish and determine if each element returns to itself in <=m steps. If any element is not reachable in <=m steps, then you have a duplicate and can return false. Otherwise, when you finish visiting all elements, you can return true:

     for (int start_index= 0; start_indexm) { return false; } } return true; 

    You can optimize this by storing additional information:

    1. Record sum of the length of the cycle from each element, unless the cycle visits an element before that element, call it sum_of_steps .
    2. For every element, only step m-sum_of_steps nodes out. If you don't return to the starting element and you don't visit an element before the starting element, you have found a loop containing duplicate elements and can return false .

    This is still O(n^2), eg {1, 2, 3, 0, 5, 6, 7, 4} , but it's a little bit faster.

    ciphwn has it right. It is all to do with statistics. What the question is asking is, in statistical terms, is whether or not the sequence of numbers form a discrete uniform distribution. A discrete uniform distribution is where all values of a finite set of possible values are equally probable. Fortunately there are some useful formulas to determine if a discrete set is uniform. Firstly, to determine the mean of the set (a..b) is (a+b)/2 and the variance is (nn-1)/12. Next, determine the variance of the given set:

     variance = sum [i=1..n] (f(i)-mean).(f(i)-mean)/n 

    and then compare with the expected variance. This will require two passes over the data, once to determine the mean and again to calculate the variance.

    Referências:

    • uniform discrete distribution
    • variance

    Here is a solution in O(N) time and O(1) extra space for finding duplicates :-

     public static boolean check_range(int arr[],int n,int m) { for(int i=0;i=m) return(false); } System.out.println("In range"); int j=0; while(j 

    Explanation:-

    1. Bring number to range (0,m-1) by arr[i] = arr[i] - n if out of range return false.
    2. for each i check if arr[arr[i]] is unoccupied that is it has value less than m
    3. if so swap(arr[i],arr[arr[i]]) and arr[arr[i]] = arr[arr[i]] + m to signal that it is occupied
    4. if arr[j] = j and simply add m and increment j
    5. if arr[arr[j]] >=m means it is occupied hence current value is duplicate hence return false.
    6. if arr[j] >= m then skip