Algoritma: cara yang efisien untuk menghapus duplikat bilangan bulat dari array

Saya mendapat masalah ini dari wawancara dengan Microsoft.

Diberikan larik bilangan bulat acak, tulis algoritme dalam C yang menghapus bilangan duplikat dan mengembalikan bilangan unik dalam larik asli.

Misalnya Input: {4, 8, 4, 1, 1, 2, 9} Output:{4, 8, 1, 2, 9, ?, ?}

Satu peringatan adalah bahwa algoritme yang diharapkan tidak memerlukan array untuk diurutkan terlebih dahulu. Dan ketika sebuah elemen telah dihilangkan, elemen berikut harus digeser ke depan juga. Bagaimanapun, nilai elemen di ekor larik tempat elemen digeser ke depan dapat diabaikan.

Pembaruan: Hasil harus dikembalikan dalam larik asli dan struktur data pembantu (mis. Hashtable) tidak boleh digunakan. Namun, saya kira pelestarian pesanan tidak perlu.

Pembaruan2: Bagi mereka yang bertanya-tanya mengapa kendala tidak praktis ini, ini adalah pertanyaan wawancara dan semua kendala ini dibahas selama proses berpikir untuk melihat bagaimana saya bisa mendapatkan ide yang berbeda.

Bagaimana tentang:

void rmdup(int *array, int length)
{
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }
}

Harus O (n ^ 2) atau kurang.

Solusi yang disarankan oleh pacar saya adalah variasi jenis gabungan. Satu-satunya modifikasi adalah selama langkah penggabungan, abaikan saja nilai duplikat. Solusi ini juga akan menjadi O (n log n). Dalam pendekatan ini, penghapusan pengurutan / duplikasi digabungkan bersama. Namun, saya tidak yakin apakah itu membuat perbedaan.

Saya telah memposting ini sekali sebelumnya di SO, tetapi saya akan mereproduksinya di sini karena itu cukup keren. Ini menggunakan hashing, membangun sesuatu seperti set hash di tempat. Ini dijamin menjadi O (1) di ruang ketiak (rekursi adalah panggilan ekor), dan biasanya kompleksitas waktu O (N). Algoritmanya adalah sebagai berikut:

1. Ambil elemen pertama dari array, ini akan menjadi sentinelnya.
2. Susun ulang sisa larik, sebanyak mungkin, sedemikian rupa sehingga setiap elemen berada pada posisi yang sesuai dengan hashnya. Saat langkah ini selesai, duplikat akan ditemukan. Atur mereka sama dengan sentinel.
3. Pindahkan semua elemen yang indeksnya sama dengan hash ke awal larik.
4. Pindahkan semua elemen yang sama dengan sentinel, kecuali elemen pertama dari larik, ke akhir larik.
5. Apa yang tersisa antara elemen yang di-hash dengan benar dan elemen duplikat adalah elemen yang tidak dapat ditempatkan di indeks yang sesuai dengan hashnya karena benturan. Berulang kali untuk menangani elemen-elemen ini.

Ini dapat diperlihatkan sebagai O (N) asalkan tidak ada skenario patologis dalam hashing: Bahkan jika tidak ada duplikat, kira-kira 2/3 dari elemen akan dihilangkan pada setiap rekursi. Setiap level rekursi adalah O (n) dimana n kecil adalah jumlah elemen yang tersisa. Satu-satunya masalah adalah, dalam praktiknya, ini lebih lambat daripada pengurutan cepat ketika hanya ada sedikit duplikat, yaitu banyak tabrakan. Namun, bila ada banyak duplikat, itu luar biasa cepat.

Sunting: Dalam implementasi D saat ini, hash_t adalah 32 bit. Segala sesuatu tentang algoritma ini mengasumsikan bahwa akan ada sangat sedikit, jika ada, benturan hash dalam ruang 32-bit penuh. Tabrakan, bagaimanapun, dapat sering terjadi di ruang modulus. Namun, asumsi ini kemungkinan besar akan benar untuk kumpulan data yang berukuran wajar. Jika kunci kurang dari atau sama dengan 32 bit, itu bisa menjadi hashnya sendiri, yang berarti tabrakan di ruang 32-bit penuh tidak mungkin terjadi. Jika lebih besar, Anda tidak bisa memasukkan cukup banyak ke dalam ruang alamat memori 32-bit karena itu menjadi masalah. Saya berasumsi hash_t akan ditingkatkan menjadi 64 bit dalam implementasi 64-bit D, di mana kumpulan data bisa lebih besar. Selain itu, jika ini terbukti menjadi masalah, seseorang dapat mengubah fungsi hash di setiap tingkat rekursi.

Berikut implementasi dalam bahasa pemrograman D:

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}

Satu implementasi yang lebih efisien

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

Dalam implementasi ini tidak diperlukan pengurutan array. Juga jika elemen duplikat ditemukan, tidak perlu menggeser semua elemen setelah ini dengan satu posisi.

Output dari kode ini adalah array [] dengan ukuran NewLength

Di sini kita mulai dari elemt ke-2 dalam larik dan membandingkannya dengan semua elemen dalam larik hingga larik ini. Kami memegang variabel indeks tambahan 'NewLength' untuk memodifikasi array input. Variabel NewLength diinisialisasi ke 0.

Elemen dalam larik [1] akan dibandingkan dengan larik [0]. Jika berbeda, maka nilai dalam array [NewLength] akan diubah dengan array [1] dan increment NewLength. Jika sama, NewLength tidak akan diubah.

Jadi jika kita memiliki array [1 2 1 3 1], maka

Pada first pass loop 'j', array [1] (2) akan dibandingkan dengan array0, kemudian 2 akan ditulis menjadi array [NewLength] = array [1] sehingga array akan menjadi [1 2] karena NewLength = 2

Pada lintasan kedua loop 'j', larik [2] (1) akan dibandingkan dengan larik0 dan larik1. Di sini karena array [2] (1) dan array0 adalah loop yang sama akan putus di sini. jadi array akan menjadi [1 2] karena NewLength = 2

dan seterusnya

Jika Anda mencari notasi-O superior, maka mengurutkan array dengan pengurutan O (n log n) kemudian melakukan penjelajahan O (n) mungkin merupakan rute terbaik. Tanpa penyortiran, Anda melihat O (n ^ 2).

Edit: jika Anda hanya melakukan integer, maka Anda juga dapat melakukan penyortiran radix untuk mendapatkan O (n).

1. Menggunakan O (1) spasi ekstra, dalam waktu O (n log n)

Ini dimungkinkan, misalnya:

• pertama lakukan penyortiran O (n log n) di tempat
• kemudian telusuri daftarnya sekali, tulis contoh pertama dari setiap kembali ke awal daftar

Saya yakin partner ejel benar bahwa cara terbaik untuk melakukan ini adalah dengan melakukan penggabungan di tempat dengan langkah penggabungan yang disederhanakan, dan mungkin itulah maksud dari pertanyaannya, jika Anda misalnya. menulis fungsi pustaka baru untuk melakukan ini seefisien mungkin tanpa kemampuan untuk meningkatkan masukan, dan ada kasus akan berguna untuk melakukannya tanpa tabel hash, tergantung pada jenis masukan. Tapi saya belum benar-benar memeriksanya.

2. Menggunakan ruang ekstra O (banyak), dalam waktu O (n)

• mendeklarasikan array nol yang cukup besar untuk menampung semua bilangan bulat
• berjalan melalui array sekali
• setel elemen array yang sesuai ke 1 untuk setiap bilangan bulat.
• Jika sudah 1, lewati bilangan bulat itu.

Ini hanya berfungsi jika beberapa asumsi yang dipertanyakan berlaku:

• mungkin untuk nol memori dengan murah, atau ukuran intnya kecil dibandingkan dengan jumlah mereka
• Anda dengan senang hati meminta memori 256 ^ sizepof (int) OS Anda
• dan itu akan menyimpannya untuk Anda dengan sangat efisien jika ukurannya sangat besar

Ini jawaban yang buruk, tetapi jika Anda memiliki BANYAK elemen masukan, tetapi semuanya adalah bilangan bulat 8-bit (atau mungkin bahkan bilangan bulat 16-bit), ini bisa menjadi cara terbaik.

3. O (sedikit) -ish extra space, O (n) -ish time

Sebagai # 2, tetapi gunakan tabel hash.

4. Cara yang jelas

Jika jumlah elemennya kecil, menulis algoritme yang sesuai tidak berguna jika kode lain lebih cepat ditulis dan lebih cepat dibaca.

Misalnya. Telusuri larik untuk setiap elemen unik (mis. Elemen pertama, elemen kedua (duplikat dari yang pertama telah dihapus) dll) menghapus semua elemen yang identik. O (1) spasi ekstra, O (n ^ 2) waktu.

Misalnya. Gunakan fungsi perpustakaan yang melakukan ini. efisiensi tergantung yang Anda miliki dengan mudah.

Nah, implementasi dasarnya cukup sederhana. Pergi melalui semua elemen, periksa apakah ada duplikat di yang tersisa dan geser sisanya ke atasnya.

Ini sangat tidak efisien dan Anda bisa mempercepatnya dengan helper-array untuk keluaran atau pengurutan / pohon biner, tetapi ini tampaknya tidak diizinkan.

Jika Anda diizinkan menggunakan C ++, panggilan ke std::sortdiikuti dengan panggilan ke std::uniqueakan memberi Anda jawabannya. Kompleksitas waktu adalah O (N log N) untuk pengurutan dan O (N) untuk traversal unik.

Dan jika C ++ tidak ada, tidak ada yang mencegah algoritme yang sama ini ditulis di C.

Anda dapat melakukan ini dalam sekali traversal, jika Anda bersedia mengorbankan ingatan. Anda dapat menghitung apakah Anda telah melihat integer atau tidak dalam array hash / asosiatif. Jika Anda telah melihat angka, hapus saat Anda pergi, atau lebih baik lagi, pindahkan angka yang belum Anda lihat ke dalam larik baru, hindari pergeseran dalam larik asli.

Di Perl:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}

Nilai yang dikembalikan dari fungsi tersebut harus berupa jumlah elemen unik dan semuanya disimpan di depan larik. Tanpa informasi tambahan ini, Anda bahkan tidak akan tahu jika ada duplikat.

Setiap iterasi dari loop luar memproses satu elemen dari array. Jika unik, ia tetap berada di depan larik dan jika itu duplikat, ia ditimpa oleh elemen terakhir yang belum diproses dalam larik. Solusi ini berjalan dalam waktu O (n ^ 2).

#include <stdio.h>
#include <stdlib.h>

size_t rmdup(int *arr, size_t len)
{
  size_t prev = 0;
  size_t curr = 1;
  size_t last = len - 1;
  while (curr <= last) {
    for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
    if (prev == curr) {
      ++curr;
    } else {
      arr[curr] = arr[last];
      --last;
    }
  }
  return curr;
}

void print_array(int *arr, size_t len)
{
  printf("{");
  size_t curr = 0;
  for (curr = 0; curr < len; ++curr) {
    if (curr > 0) printf(", ");
    printf("%d", arr[curr]);
  }
  printf("}");
}

int main()
{
  int arr[] = {4, 8, 4, 1, 1, 2, 9};
  printf("Before: ");
  size_t len = sizeof (arr) / sizeof (arr[0]);
  print_array(arr, len);
  len = rmdup(arr, len);
  printf("\nAfter: ");
  print_array(arr, len);
  printf("\n");
  return 0;
}

Ini adalah Versi Java.

int[] removeDuplicate(int[] input){

        int arrayLen = input.length;
        for(int i=0;i<arrayLen;i++){
            for(int j = i+1; j< arrayLen ; j++){
                if(((input[i]^input[j]) == 0)){
                    input[j] = 0;
                }
                if((input[j]==0) && j<arrayLen-1){
                        input[j] = input[j+1];
                        input[j+1] = 0;
                    }               
            }
        }       
        return input;       
    }

Inilah solusi saya.

///// find duplicates in an array and remove them

void unique(int* input, int n)
{
     merge_sort(input, 0, n) ;

     int prev = 0  ;

     for(int i = 1 ; i < n ; i++)
     {
          if(input[i] != input[prev])
               if(prev < i-1)
                   input[prev++] = input[i] ;                         
     }
}

Sebuah array jelas harus "dilintasi" dari kanan ke kiri untuk menghindari penyalinan nilai yang tidak perlu bolak-balik.

Jika Anda memiliki memori tak terbatas, Anda dapat mengalokasikan larik bit untuk sizeof(type-of-element-in-array) / 8byte agar setiap bit menandakan apakah Anda telah menemukan nilai yang sesuai atau belum.

Jika tidak, saya tidak bisa memikirkan hal yang lebih baik daripada melintasi larik dan membandingkan setiap nilai dengan nilai yang mengikutinya dan kemudian jika duplikat ditemukan, hapus nilai-nilai ini sama sekali. Ini ada di suatu tempat di dekat O (n ^ 2) (atau O ((n ^ 2-n) / 2) ).

IBM memiliki artikel tentang subjek yang agak dekat.

Ayo lihat:

• O (N) lulus untuk menemukan alokasi min / maks
• bit-array untuk ditemukan
• O (N) lulus menukar duplikat ke akhir.

Ini dapat dilakukan dalam sekali jalan dengan algoritma O (N log N) dan tanpa penyimpanan ekstra.

Lanjutkan dari elemen a[1]ke a[N]. Pada setiap tahap i, semua elemen ke kiri dari a[i]terdiri diurutkan tumpukan elemen a[0]melalui a[j]. Sementara itu, indeks kedua j, awalnya 0, melacak ukuran heap.

Periksa a[i]dan sisipkan ke heap, yang sekarang menempati elemen a[0]ke a[j+1]. Saat elemen dimasukkan, jika elemen duplikat a[k]ditemukan memiliki nilai yang sama, jangan masukkan a[i]ke dalam heap (yaitu, buang); jika tidak, masukkan ke dalam heap, yang sekarang berkembang menjadi satu elemen dan sekarang terdiri a[0]dari a[j+1], dan increment j.

Lanjutkan dengan cara ini, incrementing isampai semua elemen array telah diperiksa dan dimasukkan ke dalam tumpukan, yang berakhir menempati a[0]ke a[j]. jadalah indeks elemen terakhir dari heap, dan heap hanya berisi nilai elemen unik.

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

Melihat contoh, ini bukanlah yang diminta karena larik yang dihasilkan mempertahankan urutan elemen asli. Tetapi jika persyaratan ini dilonggarkan, algoritma di atas harus melakukan triknya.

Di Jawa saya akan menyelesaikannya seperti ini. Tidak tahu bagaimana menulis ini di C.

   int length = array.length;
   for (int i = 0; i < length; i++) 
   {
      for (int j = i + 1; j < length; j++) 
      {
         if (array[i] == array[j]) 
         {
            int k, j;
            for (k = j + 1, l = j; k < length; k++, l++) 
            {
               if (array[k] != array[i]) 
               {
                  array[l] = array[k];
               }
               else
               {
                  l--;
               }
            }
            length = l;
         }
      }
   }

Bagaimana dengan berikut ini?

int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
    for(y=0;y<count;y++)
    {
        if(*(temp+y)==*(array+x))
        {
            break;
        }
    }
    if(y==count)
    {
        *(temp+count) = *(array+x);
        count++;
    }
}
memcpy(array, temp, sizeof(int)*len);

Saya mencoba untuk mendeklarasikan array temp dan memasukkan elemen ke dalamnya sebelum menyalin semuanya kembali ke array asli.

Setelah masalah ditinjau, berikut adalah cara delphi saya, yang mungkin membantu

var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;

for I := 0 to C-1 do
begin
  for J := I+1 to C-1 do
    if A[I]=A[J] then
    begin
      for K := C-1 Downto J do
        if A[J]<>A[k] then
        begin
          P:=A[K];
          A[K]:=0;
          A[J]:=P;
          C:=K;
          break;
        end
        else
        begin
          A[K]:=0;
          C:=K;
        end;
    end;
end;

//tructate array
setlength(A,C);
end;

Contoh berikut akan menyelesaikan masalah Anda:

def check_dump(x):
   if not x in t:
      t.append(x)
      return True

t=[]

output = filter(check_dump, input)

print(output)
True

import java.util.ArrayList;


public class C {

    public static void main(String[] args) {

        int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};

        ArrayList<Integer> arr1 = new ArrayList<Integer>();

        for(int i=0;i<arr.length-1;i++){

            if(arr[i] == arr[i+1]){
                arr[i] = 99999;
            }
        }

        for(int i=0;i<arr.length;i++){
            if(arr[i] != 99999){

                arr1.add(arr[i]);
            }
        }

        System.out.println(arr1);
}
    }

Ini adalah solusi naif (N * (N-1) / 2). Ini menggunakan ruang tambahan yang konstan dan mempertahankan urutan aslinya. Ini mirip dengan solusi oleh @Byju, tetapi tidak menggunakan if(){}blok. Ini juga menghindari penyalinan elemen ke dirinya sendiri.

#include <stdio.h>
#include <stdlib.h>

int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])

size_t undup_it(int array[], size_t len)
{
size_t src,dst;

  /* an array of size=1 cannot contain duplicate values */
if (len <2) return len; 
  /* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
        size_t cur;
        for (cur=0; cur < dst; cur++ ) {
                if (array[cur] == array[src]) break;
                }
        if (cur != dst) continue; /* found a duplicate */

                /* array[src] must be new: add it to the list of non-duplicates */
        if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
        dst++;
        }
return dst; /* number of valid alements in new array */
}

void print_it(int array[], size_t len)
{
size_t idx;

for (idx=0; idx < len; idx++)  {
        printf("%c %d", (idx) ? ',' :'{' , array[idx] );
        }
printf("}\n" );
}

int main(void) {    
    size_t cnt = COUNT;

    printf("Before undup:" );    
    print_it(numbers, cnt);    

    cnt = undup_it(numbers,cnt);

    printf("After undup:" );    
    print_it(numbers, cnt);

    return 0;
}

Hal ini dapat dilakukan dalam sekali jalan, dalam waktu O (N) dalam jumlah bilangan bulat dalam daftar input, dan penyimpanan O (N) dalam jumlah bilangan bulat unik.

Telusuri daftar dari depan ke belakang, dengan dua penunjuk "dst" dan "src" diinisialisasi ke item pertama. Mulailah dengan tabel hash kosong dari "integers seen". Jika integer di src tidak ada di hash, tuliskan ke slot di dst dan increment dst. Tambahkan bilangan bulat di src ke hash, lalu tambahkan src. Ulangi sampai src melewati akhir daftar masukan.

Sisipkan semua elemen dalam binary tree the disregards duplicates- O(nlog(n)). Kemudian ekstrak semuanya kembali ke dalam array dengan melakukan traversal - O(n). Saya berasumsi bahwa Anda tidak perlu pelestarian pesanan.

Gunakan filter mekar untuk hashing. Ini akan mengurangi overhead memori secara signifikan.

Di JAWA,

    Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};

    String value ="";

    for(Integer i:arrayInteger)
    {
        if(!value.contains(Integer.toString(i))){
            value +=Integer.toString(i)+",";
        }

    }

    String[] arraySplitToString = value.split(",");
    Integer[] arrayIntResult = new Integer[arraySplitToString.length];
    for(int i = 0 ; i < arraySplitToString.length ; i++){
        arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
    }

keluaran: {1, 2, 3, 4, 6, 7, 8, 9, 10}

Semoga ini bisa membantu

Buat BinarySearchTreeyang memiliki kompleksitas O (n).

Pertama, Anda harus membuat larik di check[n]mana n adalah jumlah elemen larik yang ingin Anda buat bebas duplikat dan menetapkan nilai setiap elemen (dari larik pemeriksa) sama dengan 1. Menggunakan perulangan for melintasi larik dengan duplikat, misalkan namanya arr, dan di loop-for tulis ini:

{
    if (check[arr[i]] != 1) {
        arr[i] = 0;
    }
    else {
        check[arr[i]] = 0;
    }
}

Dengan itu, Anda menyetel setiap duplikat sama dengan nol. Jadi satu-satunya hal yang harus dilakukan adalah melintasi arrarray dan mencetak semua yang tidak sama dengan nol. Urutan tetap dan membutuhkan waktu linier (3 * n).

Diberikan sebuah array dari n elemen, tulis sebuah algoritma untuk menghapus semua duplikat dari array dalam waktu O (nlogn)

Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array 
//input parameters :a[1:n], an array of n elements.

{

temp[1:n]; //an array of n elements. 

temp[i]=a[i];for i=1 to n

 temp[i].value=a[i]

temp[i].key=i

 //based on 'value' sort the array temp.

//based on 'value' delete duplicate elements from temp.

//based on 'key' sort the array temp.//construct an array p using temp.

 p[i]=temp[i]value

  return p.

Di elemen lain dipertahankan dalam larik keluaran menggunakan 'kunci'. Anggap kunci tersebut memiliki panjang O (n), waktu yang dibutuhkan untuk melakukan penyortiran pada kunci dan nilainya adalah O (nlogn). Jadi waktu yang dibutuhkan untuk menghapus semua duplikat dari array adalah O (nlogn).

inilah yang saya dapatkan, meskipun salah tempat urutannya, kita dapat mengurutkan dalam naik atau turun untuk memperbaikinya.

#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: \t");
scanf("%d",&n);
int arr[n],changedarr[n];

for(x=0;x<n;x++){
    printf("Enter a number for array[%d]: ",x);
    scanf("%d",&arr[x]);
}
printf("\nOriginal Number in an array\n");
for(x=0;x<n;x++){
    printf("%d\t",arr[x]);
}

int i=0,j=0;
// printf("i\tj\tarr\tchanged\n");

for (int i = 0; i < n; i++)
{
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    for (int j = 0; j <n; j++)
    {   
        if (i==j)
        {
            continue;

        }
        else if(arr[i]==arr[j]){
            changedarr[j]=0;

        }
        else{
            changedarr[i]=arr[i];

        }
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    }
    myvar+=1;
}
// printf("\n\nmyvar=%d\n",myvar);
int count=0;
printf("\nThe unique items:\n");
for (int i = 0; i < myvar; i++)
{
        if(changedarr[i]!=0){
            count+=1;
            printf("%d\t",changedarr[i]);   
        }
}
    printf("\n");
}

Akan keren jika Anda memiliki DataStructure yang baik yang dapat dengan cepat mengetahui apakah itu berisi bilangan bulat. Mungkin semacam pohon.

DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
  if(elementsSeen.Contains(array[i])
    elementsRemoved++;
  else
    array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;