Bagaimana cara mengekstrak nilai unik dari array secara efisien?

Saya ingin mengekstrak nilai unik dari array saya (yang dialokasikan secara dinamis). Saya punya sesuatu seperti ini:

    [0]     0   int
    [1]     1   int
    [2]     2   int
    [3]     2   int
    [4]     2   int
    [5]     5   int
    [6]     6   int
    [7]     6   int
    [8]     8   int
    [9]     9   int
    [10]    10  int
    [11]    8   int
    [12]    12  int
    [13]    10  int
    [14]    14  int
    [15]    6   int
    [16]    2   int
    [17]    17  int
    [18]    10  int
    [19]    5   int
    [20]    5   int

Saya ingin memiliki array berukuran 12 dengan setiap catatan di dalamnya menjadi nilai unik dari array lainnya.

Bagaimana saya bisa melakukan itu?

EDIT Saya lupa menyebutkan bahwa saya tidak dapat menggunakan wadah STL (seperti std::vector atau std::list)


c++ arrays element unique
person Patryk    schedule 07.02.2012    source sumber
comment
Apakah Anda mengetahui nilai maksimum dan minimum dalam array yang dialokasikan secara dinamis?   -  person Jayantha Lal Sirisena    schedule 07.02.2012
comment
@Jayantha Saya bisa mendapatkan nilai ini ya. Tapi untuk apa?   -  person Patryk    schedule 07.02.2012
comment
@Patryk: Bisakah Anda menggunakan algoritma STL?   -  person Jacob    schedule 07.02.2012
comment
@Patryk: Saya rasa pertanyaan Jayantha adalah apakah nilainya tetap dan kecil (menurut beberapa definisi kecil)... mungkin tujuannya adalah Anda dapat membuat array N bool (atau menggunakan bitmap), berjalan di atas larik O(N) yang menandai elemen yang ada. Kemudian bitmap akan berisi kumpulan nilai yang ada dalam array asli.   -  person David Rodríguez - dribeas    schedule 07.02.2012

Jawaban (6)


arrow_upward
1
arrow_downward

Pertama, Anda perlu mengurutkan array, lalu mengulangi array yang diurutkan dan memeriksa apakah entri sebelumnya atau berikutnya sama dengan entri saat ini. Jika tidak maka nilainya unik.

Sunting: Saya mungkin salah memahami pertanyaannya... Salah satu cara untuk mendapatkan apa yang Anda inginkan adalah dengan mengulangi array. Untuk setiap nilai, periksa nilai yang sudah ada di array lain, jika belum salin di sana. Hal ini mungkin harus dilakukan dalam dua langkah, langkah pertama untuk mendapatkan jumlah entri unik (menggunakan array dengan ukuran yang sama dengan yang sudah ada) dan langkah pertama untuk mendapatkan array dengan ukuran yang benar.

person Some programmer dude    schedule 07.02.2012

arrow_upward
5
arrow_downward

Gunakan std::unique setelah mengurutkan array dengan algoritme pengurutan favorit Anda (mis. std::sort)

Edit: Tanpa STL, solusi paling sederhana adalah menemukan nilai min & maks dalam array dan secara dinamis mengalokasikan array bool. Lintasi array dan jika Anda melihat elemennya, setel elemen bool yang sesuai ke true. Alokasikan array int baru dengan jumlah total elemen unik dan isi dengan data dari array bool.

Direkomendasikan: Urutkan array dan hapus elemen yang berurutan. Menerapkan pengurutan cepat tidak terlalu sulit, dan jika Anda berurusan dengan bilangan bulat, pengurutan radix mungkin lebih baik.

person Jacob    schedule 07.02.2012

arrow_upward
2
arrow_downward

Anda dapat menggunakan std::set. Tambahkan semua elemen ke dalamnya, pada akhirnya hanya nilai unik yang akan muncul.

person Luchian Grigore    schedule 07.02.2012

arrow_upward
1
arrow_downward 

#include <iostream>
#include <stdlib.h>
using namespace std;

int cmpfun(const void * a, const void * b){
  return (*(int*)a - *(int*)b);
}
int main(){
  int n,i,j=0;
  cout<<"Enter the number of elements in the array:\n";
  cin>>n;
  int arr[n],arr_new[n];
  for(i=0;i<n;i++)
       cin>>arr[i];
  qsort(arr, n, sizeof(int), cmpfun); /*Sorting the array; if you aren't allowed to use any library sorting method,
                                   then I suggest to implement one sorting function on your own.*/

  for(i=0;i<n;i++){
       arr_new[j++]=arr[i];
        // Excluding all duplicates
       while(i<(n-1) && arr[i]==arr[i+1])
                 i++;
  }
  for(i=0;i<j;i++)
  cout<<arr_new[i]<<" ";

return 0;}

Tujuan utamanya adalah untuk memastikan duplikat diabaikan. Jadi, Anda harus mengurutkan array terlebih dahulu dan kemudian dalam waktu O(n), melintasi array, mengabaikan semua pengulangan. Saat melintasi array, salin semua nilai unik (nilai yang Anda temui pertama kali) ke array baru.

Satu-satunya hal yang menurut saya dapat menjadi perhatian Anda adalah bahwa masing-masing urutan elemen dalam array lama tidak dipertahankan dalam array baru. Namun jika Anda hanya ingin menemukan nilai unik, maka metode ini akan berfungsi dengan baik.

person Archit Kapoor    schedule 15.05.2015

arrow_upward
0
arrow_downward

Anda dapat menggunakan set hash (unordered_set) untuk menyimpan setiap nilai array sumber. Kumpulan tersebut secara otomatis hanya akan menyimpan nilai unik. Kemudian, jika Anda benar-benar membutuhkan sebuah array dan bukan sebuah himpunan, Anda dapat membuat sebuah array dengan ukuran yang baik dan mengisinya dengan elemen-elemen dari himpunan tersebut.

person Baptiste Wicht    schedule 07.02.2012

arrow_upward
0
arrow_downward

Jika Anda mengetahui maksimum dan minimum, Anda dapat membuat array baru dengan semua kemungkinan nilai yang bisa Anda peroleh dan kemudian mengulang array dinamis Anda. Untuk setiap nilai, tetapkan 1 untuk array baru dengan mengambil sebagai indeks nilai. Sebagai contoh:- katakanlah Anda memiliki data seperti ini 1,2,2,4,6

jika rentangnya 1 sampai 7

array kedua akan menjadi seperti ini

1 2 3 4 5 6 7
1 1 0 1 0 1 0

Kompleksitas algonya adalah 2n

person Jayantha Lal Sirisena    schedule 07.02.2012