Usuń duplikaty z tablicy i zapisz ją w innej

Question

Tak więc otrzymałem zadanie utworzenia tablicy bez zduplikowanych wartości z innej istniejącej tablicy. Zrobiłem to, ale chcę wiedzieć, czy istnieje inny lepszy sposób na zrobienie tego.

Przykładowe wejście / wyjście:

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

Output: 10, 15, 5, 1, 3

Oto mój kod.

#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;
}

Nie jestem pewien, czy jest to właściwy i prosty sposób, w jaki to robię. Chcę kilka sugestii.

Z góry dziękuję. :)

Answer 1

Wczesne zakończenie

Po

        dup = 1;

powinieneś break. Nie ma potrzeby wykonywania pozostałej części pętli.

Booleans

Rozważ użycie <stdbool.h>, wykonanie bool dup = false, późniejsze przypisanie truei napisanie if (!dup).

Złożoność

W praktyce tablica pięciu wartości nie pociąga za sobą żadnych kosztów obliczeniowych. Jeśli jednak twój profesor dba o analizę złożoności, "właściwe" rozwiązanie tego problemu będzie musiało zostać ukończone w czasie liniowym (a nie w bieżącym czasie kwadratowym), przy użyciu czegoś w rodzaju zestawu skrótu z pseudokodem:

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

Ten Q wymaga samodzielnej deduplikacji. Usuń duplikaty ... Ale ponieważ jest to moja trzecia wersja wewnętrznej pętli, korzystam z nowego początku.

To nieszkodliwe przypisanie int j = i + 1;, pierwotnie spakowane do listy for-expression-list, robi coś więcej niż tylko inicjalizację jostatniego i: czyni m[j]niedozwolonym / niezdefiniowanym.

Celem (?) Jest uniknięcie dupflagi i „znormalizowanie” pętli. Myślę, że to przestawienie jest tego warte:

    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 
    }

Teraz wszystko jest na swoim miejscu.

Napisałem do statement while (expr);bez nawiasów klamrowych, aby zilustrować strukturę. To, co jest nieco ukryte, to przyrost pętli if (++j....

---

Zamiast prawdziwej (posortowanej) struktury można użyć nowej unikalnej tablicy do wyszukiwania duplikatów. Ze względu na 0już w nowej tablicy najpierw bezwarunkowo kopiuję pierwszy element, a następnie zaczynam pętlę od drugiego elementu.

    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;
        }

Wciąż if (p[j] == m[i])musi to być logiczne if (j == k), więc pętla for musi być nieco freestylowana.

Do printfe przedstawiają:

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

Efekt uboczny: kolejność jest teraz zachowana.

Myślę, że jest to trochę trudne, ponieważ wyszukiwanie i wstawianie są tak ściśle powiązane. kIndeks musi być obsługiwane precyzyjnie. (inne też)

Wydajność: nie wiem nawet, czy użycie nowej macierzy do k jest szybsze niż wyszukiwanie reszty oryginału przez OP. Wydaje się, że przynajmniej w niektórych przypadkach jest to takie samo.

Problem polega na tym, że nowa tablica nie jest posortowana. Utrzymywanie tego w porządku kosztuje zbyt wiele, jeśli jest wykonywane naiwnie, po każdej wkładce.

Więc najpierw należałoby się „rozproszyć”, aby skutecznie wyszukiwać. Dla (losowych) liczb całkowitych modulo 10 może utworzyć dziesięć różnych tablic - lub pojemników. Z 2D b[][](zamiast OP p[])

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

Każda (pod) tablica potrzebuje oryginału ARRAY_SIZEw najgorszym przypadku. Ale teraz tablica do wyszukiwania duplikatów jest średnio 10 razy krótsza.

---

Możesz więc zmienić interaktywne wejście w generator tablic z milionem liczb całkowitych i wykonać kilka testów.

---

Wszystko przez tę dupflagę pętli;)