Encontre duplicatas em uma matriz

Dada uma matriz de n elementos inteiros, como você vai encontrar se há duplicatas na matriz em tempo O (n) sem usar nenhum espaço extra.

Com espaço extra, significa espaço extra de ordem O (n).

O operador Xor ajuda de alguma forma.

Se não houver informações adicionais, essa questão parece ser insolúvel, já que este é o Problema de Distinção do Elemento , que não pode ser resolvido com as restrições que você forneceu, no tempo necessário.

você pode permitir:

(1) mais memory e use um hashtable / hashset e atenda aos critérios de tempo O (n). [iterar a matriz, verifique se um elemento está na tabela de hash, se é que você tem dupes, caso contrário – insira o elemento na tabela e continue].

(2) mais tempo , classifique a matriz [O (nlogn)] e atenda aos critérios de espaço sub-linear. [Após a ordenação, percorra o array e, para cada a[i] , a[i+1] , verifique se eles são idênticos. Se você não encontrou um par idêntico, você não tem dupes]

EDIT : A prova para esta afirmação é um pouco longa, e precisa de notação matemática que não são suportados aqui (sidenote: nós realmente precisamos de suporte tex), mas a idéia é se modelarmos nosso problema como uma Árvore de Computação Algébrica (que é uma feira). suposição quando nenhum hashing é permitido, e espaço constante à disposição), então, Ben Or provou em seu artigo Lower Bounds For Algebraic Computation Trees (1983) (publicado em prestigiado ACM), que elemento distintivo é Omega(nlogn) problema sob este modelo. Lubiw mostrou que a mesma conclusão também se aplica ao limitar-nos a números inteiros em 1991: A Lower Bound for the Integer Element Distinctness Problem , mas estes artigos concluem que sob o modelo de computação de tree algébrica – Integer Distinctness Problem é Omega (nlogn) Problem .

Radix Sort in-loco seguido por Linear Scan

Algoritmo de ordenação radix in place

Dependendo do que você realmente considera a complexidade de tempo de uma sorting Radix, esta solução é O (N) time, embora minha opinião pessoal não seja assim. Eu acho que se você não fizer a suposição de tempo linear na sorting inteira, então o problema é insolúvel.

Devido ao fato de que a sorting está no local, só é necessário o armazenamento adicional de O (1).

Código é tudo C ++ 11

Passo 1: Radix Ordenar no lugar

 template::value>::type* = nullptr> void RecurseOnRadixSort(std::vector& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 < = onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template ::value>::type* = nullptr> void InPlaceRadixSort(std::vector& myArray) { int zerosEnd = -1; int onesBegin = static_cast(myArray.size()); T mask = static_cast(1) < < sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast(1) < < sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } 

Etapa 2: verificação linear para elementos duplicados

 for (size_t i=0, j=1; j 

Código Completo

 #include  #include  #include  #include  #include  #include  #include  #include  using namespace std; #define N 10 template  void PrintArray(const std::vector& myArray) { for (auto&& element : myArray) { std::cout < < element << std::endl; } } template::value>::type* = nullptr> void RecurseOnRadixSort(std::vector& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 < = onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template ::value>::type* = nullptr> void InPlaceRadixSort(std::vector& myArray) { int zerosEnd = -1; int onesBegin = static_cast(myArray.size()); T mask = static_cast(1) < < sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast(1) < < sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } int main() { srand(time(NULL)); std::vector myArray(N); for (size_t i=0;i 

Demonstração ao vivo

Aqui está uma solução interessante para este problema com uma única restrição que os elementos devem variar entre 0 e n-2 (inclusive) onde n é o número de elementos.

Isso funciona no tempo O (n) com uma complexidade de espaço O (1).

Aqui está a solução com o uso do tempo O (n) e o uso do espaço O (1)!

 Traverse the array. Do following for every index i of A[]. { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // ie, A[abs(A[i])] is negative this element (ith element of list) is a repetition } 

Créditos: Método 5 Geek for Geeks

Essa solução é baseada em uma que remove duplicatas de uma matriz por @dsimcha, como pode ser encontrado aqui .

Ele executa um algoritmo de troca no local, com hashes de valor usados ​​para trocar posições. Observe que isso destrói o conteúdo da matriz original até certo ponto. Mas não havia exigência na pergunta do OP que proibia isso.

 public static class DupFinder { public static bool HasDups(int[] array, ref int nEvals) { nEvals = 0; return DupFinder.FindInPlace(array, 0, ref nEvals); } private static bool FindInPlace(int[] array, int start, ref int nEvals) { if (array.Length - start < 2) return false; var sentinel = array[start]; var offset = start + 1; var len = array.Length - offset; for (var ndx = 0; ndx < len; nEvals++) { var cur = array[offset + ndx]; if (cur == sentinel) { ndx++; continue; } var hash = cur % len; if (ndx == hash) { ndx++; continue; } var at_hash = array[offset + hash]; if (cur == at_hash) { array[offset + ndx] = sentinel; ndx++; continue; } if (at_hash == sentinel) { Swap(array, offset, ndx, hash); ndx++; continue; } var hash_hash = at_hash % len; if (hash_hash != hash) { Swap(array, offset, ndx, hash); if (hash < ndx) ndx++; } else { ndx++; } } var swapPos = 0; for (var i = 0; i < len; i++, nEvals++) { var cur = array[offset + i]; if (cur != sentinel && i == (cur % len)) Swap(array, offset, i, swapPos++); } for (var i = swapPos; i < len; nEvals++) { var cur = array[offset + i]; if (cur == sentinel) return true; // got dups. else i++; } // Let's assume C# supports tail recursion ;-) // Then => look ma, O(1) extra storage space. return FindInPlace(array, offset + swapPos, ref nEvals); } private static void Swap(int[] array, int offset, int first, int second) { var tmp = array[offset + first]; array[offset + first] = array[offset + second]; array[offset + second] = tmp; } } 

Assim, se assumirmos por um momento que c # suporta recursion de cauda e não contamos os frameworks de pilha usados ​​como espaço extra, ele tem O (1) espaço requerido.

O autor menciona que é de complexidade de tempo O (N) -ish. Os testes (limitados) (em oposição a uma análise de complexidade computacional) que eu realizei indicariam que está mais próximo de O (N log N).

 Array Size Dup Position #Evals 12 7 26 12 - 35 100,000 80,000 279,997 100,000 - 453,441 

Para o caso geral, esse problema não parece ter solução devido às fortes restrições de complexidade e à input irrestrita.

É claro, que você precisa de pelo menos N passos para até mesmo ver toda a input. Portanto, não pode ser mais rápido que O(n) .

Agora, para certificar-se de identificar todas as duplicatas possíveis, você tem diferentes possibilidades:

  • Compare cada número com todos os outros números, isto não requer muito espaço adicional, mas toma O(n^2) time`
  • Faça a comparação de uma maneira mais inteligente, trocando os números inteiros no espaço disponível. Isso permite “armazenar informações” na própria seqüência. Na verdade, comparar todos os números entre si geralmente é feito em algoritmos de sorting . Os algoritmos de ordenação mais rápidos que não requerem espaço adicional precisam do tempo O(n log n) . A Wikipedia tem um writeup bastante longo com muitas fonts . Então você nunca pode ter seu tempo necessário dessa maneira. ( algum gráfico de comparação de algoritmos de ordenação conhecidos )
  • Você poderia fazer alguma contabilidade com um mapa de hash que pode permitir que você leve apenas tempo linear O(n) , mas essa contabilidade precisa ser armazenada em algum lugar . Caso contrário, você simplesmente “esquecerá” quais números você já viu. Infelizmente, a contabilidade exigirá mais espaço se sua input aumentar porque você tem tantos números diferentes para lembrar. Portanto, é impossível ter a mesma quantidade fixa de memory e comparar seqüências de input arbitrariamente longas. Portanto, você teria que violar o espaço constante O(1) .

Como o @Atishay aponta em sua resposta, pode haver uma solução se você tiver uma input muito restrita. Aqui é necessário que você tenha uma matriz de tamanho n e os possíveis valores estejam apenas no intervalo [0,n-2] . Este requisito garante que deve haver uma duplicata em algum lugar, porque há menos valores diferentes dos elementos na matriz. Com esse conhecimento e o intervalo muito específico de valores, você pode fazer isso. Mas isso usa suposições muito estreitas e não resolve o problema geral declarado na questão.

Editar

Conforme esclarecido nos comentários, há um limite inferior comprovado para a complexidade temporal dos algoritmos de ordenação baseados em comparação. Para referência, veja aqui:

O filtro Bloom é um hashset de espaço eficiente com uma taxa de falso positivo ajustável. A possibilidade de falso positivo significa que você tem que voltar e verificar se há uma duplicata real quando recebe um hit do BF, introduzindo um termo N ^ 2 – mas o coeficiente é ~ exp (- (espaço extra usado para o filtro)). Isso produz um espaço de troca de espaço versus tempo interessante.

Eu não tenho uma prova de que a questão como colocada é insolúvel, mas em geral “aqui está um espaço de troca interessante” é uma boa resposta para um problema insolúvel.

uma implementação usando um único int como uma variável temporária .. isto é usando vetores de bit /

  public static boolean isUniqueChars(String str) { int checker = 0; for (int i = 0; i < str.length(); ++i) { int val = str.charAt(i) - 'a'; if ((checker & (1 << val)) > 0) return false; checker |= (1 < < val); } return true; } 

ou minha implementação anterior de O (n ^ 2) sem usar qualquer variável temporária

 public static bool isDuplicate(char[] str) { if (str == null) return false; int len = str.length; if (len < 2) return false; for (int i = 1; i < len; ++i) { for (int j = 0; j < len; ++j) { if (str[i] == str[j]) return true; } } return false; } 

Exemplo limpo para determinar as duplicatas com O (n) pelo tempo e O (1) pelo espaço:

 public class DuplicateDetermineAlgorithm { public static boolean isContainsDuplicate(int[] array) { if (array == null) { throw new IllegalArgumentException("Input array can not be null"); } if (array.length < 2) { return false; } for (int i = 0; i < array.length; i++) { int pointer = convertToPositive(array[i]) - 1; if (array[pointer] > 0) { array[pointer] = changeSign(array[pointer]); } else { return true; } } return false; } private static int convertToPositive(int value) { return value < 0 ? changeSign(value) : value; } private static int changeSign(int value) { return -1 * value; } } 
 public static void getDuplicatesElements (Integer arr[]){ //Status array to track the elements if they are already considered boolean status[] = new boolean [arr.length]; //Flag to mark the element found its duplicate boolean dupFlag = false; //Output string String output = ""; //Count of duplicate elements found int count = 0; //Initialize status array with all false ie no duplicates for (int i = 0; i < arr.length; i++) { status[i] = false; } //first loop to check every element for (int i = 0; i < arr.length - 1; i++) { //Initialize every element to no duplicate dupFlag = false; //Check if this element is not already found duplicate, if not, check now. if (!status[i]){ for (int j = i+1; j < arr.length; j++){ if (arr[i] == arr[j]){ dupFlag = true; status[j] = true; } } } if (dupFlag){ output = output + " " + arr[i]; count++; } } System.out.println("Duplicate elements: " + output ); System.out.println("Count: " + count ); } 

aviso Legal

Eu não tenho uma resposta, mas meus pensamentos são muito extensos para um comentário. Além disso, eu queria escrevê-las, então as três horas que eu gasto pensando em uma solução não são completamente desperdiçadas. Espero dar-lhe um ponto de vista diferente, mas se você não gosta de perder tempo, não continue lendo. Ou apenas para baixo, vote esta resposta, vale a pena 🙂

Para dar o pontapé inicial em nosso pensamento visual, vamos ter um array de exemplo: 50 100 150 -2 -1 0 1 2 3 4 . Como você pode dizer, ele não tem duplicatas, então nosso algoritmo deve produzir FALSE . Além disso, o comprimento é 10 .

Etapa A: Contar no tempo O (N)

Vamos ignorar a restrição de memory extra por enquanto (na verdade, violar muito mal, assumindo que podemos ter memory adicional O(\inf) 🙂 e salvar em um array infinito fictício (também é duplamente infinito, já que permite indeces negativos também) as contagens para cada inteiro. Para nossa input, esta matriz ficaria assim:

 ...000001111111000...00100...00100...001000000... ^ ^ ^ [index -2] [index 50] [index 150] 

Se algum dos elementos da matriz for maior que 1 , então temos uma duplicata e o algoritmo deve retornar TRUE .

Etapa B: Mapear -inf..inf para 0..N no tempo O (N)

Vamos supor que temos um mapa f(x):-inf..inf -> 0..N que pode comprimir nosso array infinito em um array de tamanho N, e além disso fazê-lo no tempo O (N). É isso que o hashing idealmente faz. Note que não nos importamos em manter a ordem do array, pois apenas nos importamos se ele possui elementos que estão acima de 1. Assim, podemos combinar esses dois passos e eliminar a necessidade de memory inifinita – yay! Ainda estamos usando uma memory O (N) adicional (na verdade, exatamente N contagens) para manter os valores de contagem. O próximo passo seria se livrar disso.

Etapa C: Usando o primeiro elemento como um switch

Antes de explicar este passo, perceba que realmente não precisamos armazenar nenhuma contagem maior que 1. Na primeira vez que queremos aumentar um contador e percebemos que ele já tem o valor de 1, sabemos que encontramos um duplicado! Então 1 bit de memory por contador é suficiente. Isso reduz a memory necessária para O (lg (N)), mas não nos importamos com isso, já que não é bom o suficiente. A parte importante é que 1 bit de memory por contador é suficiente.

Agora vamos explorar o fato de que podemos modificar nosso array de input. Passamos pelo array e xor todos os elementos com o valor do primeiro elemento. Se o resultado for menor que o valor antes da operação, nós o alteramos para esse resultado. Também armazenamos o primeiro elemento separadamente como sw a um custo adicional de memory O (1).

Agora, podemos usar o primeiro elemento armazenado sw e o array transformado para codificar nas contagens a partir do passo de contagem (passos A + B) da seguinte maneira: considerando o elemento com índice k de A , se A[f(A[k])] < A[f(A[k])] xor sw então a contagem é zero que significa que o elemento que estamos considerando - A[k] - não foi visto antes, então mudamos A[f(A[k])] para A[f(A[k])] xor sw . Se, de outro modo, A[f(A[k])] > A[f(A[k])] xor sw , a contagem é one que significa que o elemento que estamos considerando - A[k] - já foi visto antes , então é uma duplicata.

Assumindo o mapa:

 f(-2 xr 50) -> 0 f(-1 xr 50) -> 1 f(0) -> 2 f(1) -> 3 f(2) -> 4 f(3) -> 5 f(4) -> 6 f(86) -> 7 f(150) -> 8 f(1337) -> 9 

e depois de executar as etapas na seguinte ordem: step c; step a+b step c; step a+b o array de input se parece com isto:

 50(0) 100(86) 150(164) -2(-2 xr 50) -1(-1 xr 50) 0(50) 1(51) 2(48) 3(49) 4(54) [intermediate state, not stored in memory] 0 86 150 -2 xr 50 -1 xr 50 0 1 2 3 4 [state after step c] 0 86 *164* -2 xr 50 -1 xr 50 0 1 2 3 4 [counted element 0] 0 86 164 -2 xr 50 -1 xr 50 0 1 *48* 3 4 [counted element 1] 0 86 164 -2 xr 50 -1 xr 50 0 1 48 *49* 4 [counted element 2] *50* 86 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 3] 50 *100* 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 4] 50 100 !164! -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 5] 

Tentando contar o elemento com o índice 5 que é 0 , vemos que já havia um 0 na matriz! (porque A[f(A[5])] é 164 que é maior que 164 xr 50 ) Então, saímos TRUE e o algoritmo termina.

Moral da história

Se não formos permitidos suficiente memory x time estaremos fadados a esquecer algo e cometer um erro.

Desculpa

Infelizmente, não temos uma function hash perfeita, e não podemos simplesmente criar memory a partir do nada, então uma abordagem tradicional não funcionaria sob as restrições necessárias. O algoritmo para o qual a resposta dada pelo OP aponta pode ser modificado de modo que permita usar números que interpretados como indeces de matriz ficariam fora dos limites da matriz, dada uma function hash perfeita. Mas, mesmo assim, tem que ser inventado como usá-lo para detectar duplicação, ao invés de encontrar um garantido para existir ...

Enfim, problema interessante.

 import java.util.HashSet; import java.util.Set; public class FindDups { public static void main(String[] args) { int a[]={1,2,3,3,4}; Set s=new HashSet(); for(int i=0;i