Hapus duplikat dari array dan simpan ke yang lain

Question

Jadi saya telah ditugaskan untuk membuat array tanpa nilai duplikat dari array lain yang sudah ada. Jadi saya melakukannya, tetapi saya ingin tahu apakah ada cara lain yang lebih baik untuk melakukannya.

Contoh masukan / keluaran:

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

Output: 10, 15, 5, 1, 3

Jadi inilah kode saya.

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

Saya tidak yakin apakah ini cara yang benar dan sederhana untuk saya lakukan. Saya ingin beberapa saran.

Terima kasih sebelumnya. :)

Answer 1

Pengakhiran dini

Setelah

        dup = 1;

kamu harus break. Tidak perlu menjalankan sisa loop.

Boolean

Pertimbangkan untuk menggunakan <stdbool.h>, membuat bool dup = false, kemudian menugaskannya true, dan menulis if (!dup).

Kompleksitas

Dalam istilah praktis, larik lima nilai tidak menimbulkan biaya komputasi. Namun, jika profesor Anda peduli dengan analisis kompleksitas, solusi yang "tepat" untuk ini perlu diselesaikan dalam waktu linier (bukan waktu kuadrat Anda saat ini), menggunakan sesuatu seperti himpunan hash, dengan pseudocode:

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

Q ini membutuhkan beberapa dedup sendiri. Hapus duplikat ... Tetapi karena ini adalah versi ketiga saya dari lingkaran dalam, saya memanfaatkan awal yang baru.

Penugasan tidak ofensif ini int j = i + 1;, awalnya dikemas ke dalam daftar-untuk-ekspresi, melakukan lebih dari sekadar menginisialisasi juntuk i: itu membuat m[j]ilegal / tidak ditentukan.

Tujuan (?) Adalah untuk menghindari dupflag dan untuk "menormalkan" loop. Saya pikir penataan ulang ini sangat berharga:

    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 
    }

Sekarang semuanya ada di tempat yang alami.

Saya menulis do statement while (expr);tanpa kawat gigi untuk mengilustrasikan strukturnya. Apa yang agak tersembunyi adalah kenaikan loop if (++j....

---

Alih-alih struktur nyata (diurutkan), seseorang dapat menggunakan larik unik baru untuk mencari duplikat. Karena 0sudah ada di array baru saya pertama menyalin elemen pertama tanpa syarat, dan kemudian memulai loop dengan elemen kedua.

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

Tetap saja ini if (p[j] == m[i])harus secara logis setelahnya if (j == k), jadi loop-for harus sedikit bebas.

The printfs menggambarkan:

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

Efek samping: tatanan sekarang dipertahankan.

Saya kira ini agak rumit karena pencarian dan penyisipan sangat erat kaitannya. The kIndeks harus ditangani secara tepat. (yang lainnya juga)

Kinerja: Saya bahkan tidak tahu apakah menggunakan array baru hingga k lebih cepat daripada OP mencari sisa aslinya. Tampaknya jumlahnya sama setidaknya untuk beberapa kasus.

Masalahnya adalah array baru tidak diurutkan. Menjaga agar disortir membutuhkan biaya terlalu banyak jika dilakukan secara naif, setelah setiap penyisipan.

Jadi, seseorang harus "menyebar" terlebih dahulu untuk mencari secara efisien. Untuk bilangan bulat (acak), modulo 10 dapat membuat sepuluh larik berbeda - atau keranjang. Dengan 2D b[][](bukan OP p[])

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

Setiap (sub) larik membutuhkan yang asli ARRAY_SIZEuntuk kasus terburuk. Tapi sekarang larik untuk mencari dups rata-rata 10 kali lebih pendek.

---

Jadi Anda dapat mengubah input interaktif menjadi generator array satu juta bilangan bulat dan melakukan beberapa pengujian.

---

Semua karena dupbendera lingkaran itu;)