Entfernen Sie Duplikate aus dem Array und speichern Sie sie in einem anderen

Question

Daher wurde ich beauftragt, ein Array ohne doppelte Werte aus einem anderen vorhandenen Array zu erstellen. Also habe ich es getan, aber ich möchte wissen, ob es einen anderen besseren Weg gibt, das zu tun.

Beispiel für eine Ein- / Ausgabe:

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

Output:: 10, 15, 5, 1, 3

Also hier ist mein Code.

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

Ich bin mir nicht sicher, ob dies der richtige und einfache Weg ist, wie ich das mache. Ich möchte einige Vorschläge.

Danke im Voraus. :) :)

Answer 1

Vorzeitige Beendigung

Nach

        dup = 1;

du solltest break. Der Rest der Schleife muss nicht ausgeführt werden.

Boolesche Werte

Erwägen Sie, es zu verwenden <stdbool.h>, zu erstellen bool dup = false, später zuzuweisen trueund zu schreiben if (!dup).

Komplexität

In der Praxis verursacht ein Array von fünf Werten keine Rechenkosten. Wenn sich Ihr Professor jedoch um die Komplexitätsanalyse kümmert, muss die "richtige" Lösung hierfür in linearer Zeit (anstelle Ihrer aktuellen quadratischen Zeit) unter Verwendung einer Art Hash-Menge mit Pseudocode abgeschlossen werden:

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

Dieses Q benötigt selbst etwas Dedup. Duplikate entfernen ... Da dies jedoch meine dritte Version der inneren Schleife ist, nutze ich einen Neuanfang.

Diese harmlose Zuweisung int j = i + 1;, die ursprünglich in die For-Expression-Liste gepackt wurde, initialisiert nicht nur jdas letzte i: Sie macht m[j]illegal / undefiniert.

Das Ziel (?) Ist es, die dupFlagge zu umgehen und die Schleifen zu "normalisieren". Ich denke, diese Neuordnung lohnt sich:

    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 
    }

Jetzt ist alles am natürlichen Ort.

Ich schrieb do statement while (expr);ohne Klammern, um die Struktur zu veranschaulichen. Was ein bisschen versteckt ist, ist das Schleifeninkrement if (++j....

---

Anstelle einer realen (sortierten) Struktur kann das neue eindeutige Array verwendet werden, um nach Duplikaten zu suchen. Aufgrund des 0bereits im neuen Array vorhandenen kopiere ich zuerst das erste Element bedingungslos und beginne dann die Schleife mit dem zweiten Element.

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

Dies if (p[j] == m[i])muss jedoch logisch erfolgen if (j == k), sodass die for-Schleife ein wenig freestyled werden muss.

Die printfs veranschaulichen:

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

Nebeneffekt: Die Reihenfolge bleibt nun erhalten.

Ich denke, das ist etwas schwierig, weil das Suchen und Einfügen so eng miteinander verbunden sind. Der kIndex muss präzise behandelt werden. (die anderen auch)

Leistung: Ich weiß nicht einmal, ob die Verwendung des neuen Arrays bis zu k schneller ist als die OP-Suche im Rest des Originals. Zumindest in einigen Fällen scheint es dasselbe zu sein.

Problem ist, dass das neue Array nicht sortiert ist. Die Sortierung kostet nach jeder Einfügung zu viel, wenn sie naiv erfolgt.

Man müsste sich also zuerst "ausbreiten", um effizient suchen zu können. Für (zufällige) Ganzzahlen kann Modulo 10 zehn verschiedene Arrays - oder Buckets - erstellen. Mit einem 2D b[][](anstelle von OP p[])

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

Jedes (Unter-) Array benötigt ARRAY_SIZEim schlimmsten Fall das Original . Aber jetzt ist das Array für die Suche nach Dups im Durchschnitt zehnmal kürzer.

---

Sie können also die interaktive Eingabe in einen Array-Generator mit einer Million Ganzzahlen ändern und einige Tests durchführen.

---

Alles wegen dieser dupSchleifenflagge;)