Làm thế nào để trích xuất một cách hiệu quả các giá trị duy nhất từ ​​mảng?

Question

Tôi muốn trích xuất các giá trị duy nhất từ ​​mảng (được phân bổ động) của tôi. Tôi có một cái gì đó như thế này:

[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 

Tôi muốn có mảng 12 với mỗi bản ghi trong đó là giá trị duy nhất tạo thành mảng khác.

Tôi có thể làm như thế nào?

EDIT tôi quên đề cập đến mà tôi không thể sử dụng STL container (như std::vector hoặc std::list)

Answer 1

Trước tiên, bạn cần phải sắp xếp mảng, sau đó lặp qua mảng được sắp xếp và kiểm tra xem mục nhập trước đó hoặc tiếp theo có giống với mục nhập hiện tại hay không. Nếu không thì giá trị là duy nhất.

Chỉnh sửa: Tôi có thể đã hiểu sai câu hỏi ... Một cách để có được những gì bạn muốn là lặp qua mảng. Đối với mỗi giá trị kiểm tra giá trị đã tồn tại trong mảng khác, nếu không phải là bản sao nó có. Điều này có thể phải được thực hiện theo hai bước, một lần để có được số mục duy nhất (sử dụng một mảng có cùng kích thước với hiện tại) và một để có được một mảng có kích thước chính xác.

Answer 2

Sử dụng std::unique sau khi phân loại mảng của bạn với yêu thích thuật toán sắp xếp của bạn (ví dụ std::sort)

Chỉnh sửa: Không có STL, giải pháp đơn giản nhất là tìm giá trị tối thiểu min & trong mảng và tự động phân bổ mảng bool. Di chuyển mảng và nếu bạn thấy phần tử, hãy đặt phần tử bool tương ứng thành true. Phân bổ mảng int mới với tổng số phần tử duy nhất và điền vào dữ liệu từ mảng bool.

Được đề xuất: Sắp xếp mảng và xóa các phần tử liên tiếp. Việc triển khai sắp xếp nhanh không quá khó, và nếu bạn đang xử lý các số nguyên, radix sort có thể tốt hơn.

Answer 3

Bạn có thể sử dụng bộ băm (unordered_set) để lưu trữ từng giá trị của mảng nguồn. Bộ này sẽ tự động chỉ lưu trữ các giá trị duy nhất. Sau đó, nếu bạn thực sự cần một mảng và không phải là một tập hợp, bạn có thể tạo một mảng có kích thước tốt và điền nó với các phần tử của tập hợp.

Answer 4

Bạn có thể sử dụng std::set. Thêm tất cả các phần tử vào nó, ở phần cuối chỉ có các giá trị duy nhất sẽ có mặt.

Answer 5

Nếu bạn biết tối đa và tối thiểu bạn có thể tạo một mảng mới với tất cả các giá trị có thể bạn có thể nhận được và sau đó lặp qua mảng động của bạn. Đối với mỗi giá trị được đặt 1 cho mảng mới bằng cách lấy làm chỉ mục của giá trị. Như một ví dụ: - nói rằng bạn có dữ liệu như thế này 1,2,2,4,6

nếu phạm vi là 1-7

mảng thứ hai sẽ là như thế này

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

Sự phức tạp của các algo sẽ 2n

Answer 6

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

Mục đích chính là đảm bảo các từ khóa trùng lặp bị bỏ qua. Vì vậy, trước tiên bạn nên sắp xếp mảng và sau đó trong thời gian O (n), đi qua mảng, bỏ qua tất cả các lần lặp lại. Trong khi duyệt qua mảng, sao chép tất cả các giá trị duy nhất (giá trị mà bạn gặp lần đầu tiên) vào mảng mới.

Điều duy nhất tôi thấy có thể liên quan đến bạn là thứ tự tương ứng của các phần tử trong mảng cũ không được bảo toàn trong mảng mới. Nhưng nếu bạn chỉ quan tâm đến việc tìm kiếm các giá trị duy nhất, thì phương pháp này sẽ hoạt động tốt.