Hướng dẫn

Để đếm số phần tử khác nhau trong dãy, ta có nhiều cách làm khác nhau, sau đây là một số ý tưởng làm bài:

Cách 1: Tạo một mảng đánh dấu các phần tử xuất hiện

Phần tử nào xuất hiện trong mảng thì đánh số 1, còn phần tử nào không xuất hiện thì mặc định sẽ là 0. Khi khi đánh dấu sự xuất hiện của mảng xong, ta sẽ duyệt từ đầu tới cuối mảng đánh dấu, và đếm những vị trí có giá trị 1, và đó sẽ là kết quả của bài tập. Đô phức tạp của cách 1 là O(n), nhưng nó có nhược điểm là không sử dụng với một số quá lớn (ví dụ lớn hơn 1e6) hoặc một số âm (có thể lưu một mảng số âm ra riêng, thì vẫn dùng được nhưng vẫn bị giới hạn là lớn hơn -1e6).

Code

#include <iostream> 
#include <vector> 
using namespace std; 

int main(){
    // 1, input - lưu dữ liệu input
    int n; cin >> n; 

    vector <int> a(n); //khởi tạo một mảng động thông qua vector
    for(int i=0; i<n; ++i){
        cin >> a[i];
    }



    // 2, process - xử lí, tính toán 
    vector <int> color(1e5+1); // tạo một mảng để đánh dấu -- lưu ý độ lớn là 1e5+1, vì mảng bắt đầu từ 0 (nếu không nhớ, thì khi truy cập vượt quá chỉ số mảng sẽ bị lỗi runtime error - RTE và thoát chương trình)

    for(int i=0; i<n; ++i){
        color[a[i]]=1; 
    }


    int ans=0; // khi khởi tạo một biến, không có input thì phải gán giá trí 1, 0, -1, INT_MAX, INT_MIN phù hợp với bài tập, không thì chương trình sẽ tự tạo giá trị ngẫu nhiên và kết quả sẽ bị sai 
    for(int i=1; i<=1e5; ++i){ // lưu ý: là duyệt từ 1 tới 1e5, chứ không phải 1 tới n
        if(color[i]==1){       // lưu ý: i ở đây tương ứng với các số từ 1-1e5, không viết nhầm thành a[i] sẽ sai
            ans+=1;
        }
    }


    // 3, output - in kết quả ra màn hình
    cout <<ans <<endl; 


    return 0;

}

Cách số 2: Sử dụng các cấu trúc dữ liệu có sẵn trong thư viện STL - stander template library như map, set

Cách này code khá đơn giản, chỉ cần nhớ cú pháp của thư viện, và gọi hàm là được. Độ phức tạp của việc sử dụng set hoặc map là: O(log2N) gọi tắt là O(logN) trong lập trình, khi thêm một phần tử vào set, map. Tổng phải thêm N phần tử vào, nên độ phức tạp của cả bài là O(NlogN). Đủ nhanh để accept bài này.

Ưu điểm của phương pháp này là sử dụng thư viện có sẵn, nên code khá ngắn, không phải nghĩ nhiều. Ngoài ra có thể sử dụng với các số rất lớn hay số âm, chương trình vẫn chạy bình thường, và tốc độ vẫn bình thường. Nhược điểm là chậm hơn cách 1 thôi, nhưng vẫn khá nhanh. Code

#include <iostream> 
#include <map>
using namespace std; 

int main(){
    // 1, input
    int n; cin >> n;

    vector <int> a(n); 
    for(int i=0; i<n; ++i){
        cin >> a[i];
    }


    // 2, process
    map <int,int> m; 
    for(int i=0; i<n; ++i){
        m[a[i]]=1;
    }

    int ans=m.size();

    // 3, output
    cout <<ans <<endl; 



    return 0; 
}

Code sử dụng set

#include <iostream> 
#include <set>
using namespace std; 

int main(){
    // 1, input
    int n; cin >> n;

    vector <int> a(n); 
    for(int i=0; i<n; ++i){
        cin >> a[i];
    }


    // 2, process
    set <int> s
    for(int i=0; i<n; ++i){
        s.insert(a[i]);
    }

    int ans=s.size();

    // 3, output
    cout <<ans <<endl; 



    return 0; 
}

* Với những bài tập đã cho một mảng dữ liệu đầu vào đã được sắp xếp, cần phải biết duyệt mảng để đếm số phần tử khác biệt*

* Cái này là bài tập riêng (nhưng khá đơn giản), vì thế hãy tự nghĩ cách làm*