Remova as duplicatas do array e salve em outro

Question

Portanto, recebi a tarefa de fazer um array sem valores duplicados de outro array existente. Então, eu fiz isso, mas quero saber se existe alguma outra maneira melhor de fazer isso.

Exemplo de entrada / saída:

Input: 10, 15, 10, 5, 1, 3

Output: 10, 15, 5, 1, 3

Então aqui está meu código.

#include <stdio.h>

int main(void) {
  const int MAX_ARRAY_SIZE = 5;

  int m[MAX_ARRAY_SIZE], p[MAX_ARRAY_SIZE];


  for(int i = 0; i < MAX_ARRAY_SIZE; i++) {
    printf("Enter number: ");
    scanf("%d",&m[i]);
  }
  int k = 0;
  int dup = 0;
  for(int i =0; i < MAX_ARRAY_SIZE; i++) {
    for(int j = i +1; j <MAX_ARRAY_SIZE; j++) {
        if(m[i] == m[j]) {
            dup = 1;
        }
    }
    if(dup != 1) {
      p[k++] = m[i];
    }
    dup = 0;
  }

  printf("The new array without repeated values\n");
  for(int i = 0; i < k; i++) {
    printf("%d\n",p[i]);
  }

  return 0;
}

Não tenho certeza se esta é a maneira certa e simples de fazer isso. Eu quero algumas sugestões.

Desde já, obrigado. :)

Answer 1

Rescisão antecipada

Depois de

        dup = 1;

você deveria break. Não há necessidade de executar o resto do loop.

Booleanos

Considere usar <stdbool.h>, fazer bool dup = false, depois atribuir truee escrever if (!dup).

Complexidade

Em termos práticos, uma matriz de cinco valores não representa nenhum custo computacional. No entanto, se o seu professor se preocupa com a análise de complexidade, a solução "adequada" para isso precisa ser concluída no tempo linear (em vez do tempo quadrático atual), usando algo como um conjunto de hash, com pseudocódigo:

Set *seen = make_set();
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
    int m;
    scanf(&m);
    if (!contains(seen, m))
        add(seen, m);
}

for (m in seen)
    printf(m);

Answer 2

Este Q precisa de alguma desduplicação. Remover duplicatas ... Mas, como esta é minha terceira versão do loop interno, aproveito para começar do zero.

Esta atribuição inofensiva int j = i + 1;, originalmente compactada na lista for-expression, faz mais do que apenas inicializar jpara o último i: torna m[j]ilegal / indefinido.

O objetivo (?) É evitar a dupbandeira e "normalizar" os loops. Acho que vale a pena esse rearranjo:

    int j;
    for (int i = 0; i < ARRAY_SIZE; i++) {
        j = i;
        do
            if (++j == ARRAY_SIZE) {   // already past end?    
                p[k++] = m[i];            // copy this one
                break;                    // and finish
            }
        while (m[i] != m[j]);          // if match, then just finish 
    }

Agora tudo está no seu lugar natural.

Escrevi do statement while (expr);sem colchetes para ilustrar a estrutura. O que está um pouco oculto é o incremento do loop if (++j....

---

Em vez de uma estrutura real (ordenada), pode-se usar o novo array exclusivo para pesquisar duplicatas. Por 0já estar no novo array, primeiro copio o primeiro elemento incondicionalmente e, a seguir, começo o loop com o segundo elemento.

    int k = 1;
    /* First is always unique */
    printf("m[0] -> p[0]\n");
    p[0] = m[0];
    for (int i = 1; i < ARRAY_SIZE; i++)
        for (int j = 0;; j++) {
            if (j == k) {         
                printf("m[i=%d] -> p[k=%d]\n", i, k);
                p[k++] = m[i];
                break;
            }
            if (p[j] == m[i])
                break;
        }

Ainda assim, isso if (p[j] == m[i])tem que ser logicamente depois if (j == k), então o for-loop tem que ser um pouco livre.

Os printfs ilustram:

Enter number: 6
Enter number: 6
Enter number: 0
Enter number: 0
Enter number: 8
m[0] -> p[0]
m[i=2] -> p[k=1]
m[i=4] -> p[k=2]
The array without repeated values
6
0
8

Efeito colateral: a ordem agora é preservada.

Acho que isso é um pouco complicado porque a pesquisa e a inserção estão intimamente relacionadas. O kíndice deve ser tratado com precisão. (os outros também)

Desempenho: Eu nem sei se usar o novo array até k é mais rápido do que OP pesquisar o resto do original. Parece equivaler, pelo menos em alguns casos.

O problema é que a nova matriz não está classificada. Manter tudo ordenado custa muito caro se for feito de maneira ingênua, após cada inserção.

Portanto, seria necessário "espalhar" primeiro para pesquisar com eficiência. Para inteiros (aleatórios), o módulo 10 pode criar dez matrizes diferentes - ou intervalos. Com um 2D b[][](em vez de OP p[])

b[0] {100}
b[1] {1, 31, 20001}
b[2] {12, 32, 502}
b[3] {}
b[4] {94}
...

Cada (sub) array precisa do original ARRAY_SIZEpara o pior caso. Mas agora o array para pesquisar duplicatas é 10 vezes menor, em média.

---

Portanto, você pode alterar a entrada interativa em um gerador de array de um milhão de inteiros e fazer alguns testes.

---

Tudo por causa desse dupsinalizador de loop;)