differentNumbers

Bài tập.

Cho một vector chứa các số nguyên.

Hãy đưa ra số lượng phần tử khác nhau trong vector đó.

Ví dụ:

• Với inputVector = [1, 3, 3, 2],
  thì differentNumbers(inputVector ) = 3.
  Giải thích: Có 3 phần tử khác nhau trong vector là: 1, 3, 2
  
  
• Với inputVector = [3, 3, 3],
  thì differentNumbers(inputVector ) = 1.

Giới thiệu về set.

Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp (unique elements), và các phần tử này chính là các khóa (keys).
Ví dụ như là không tồn tại một set có  2 phần tử giống nhau như {1,2,2}, {3,4,4,4,5}.

Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép toán so sánh.
(Trong một set thì các phần tử luôn tăng dần hoặc giảm dần). Mặc định của set là các phần tử sẽ tăng dần, bạn cũng có thể viết lại hàm so sánh theo ý mình.

Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).

Lý thuyết.

Để sử dùng set ta dùng thư viện:

#include<set>

Khai báo set:

	set <Kiểu_dữ_liệu> tên_Set;
	//Ví dụ: set <int> s;

Các hàm cơ bản:

size() : trả về kích thước hiện tại của set. (Độ phức tạp O(1)).
empty() : trả về true nếu set rỗng, và ngược lại trả về false. (Độ phức tạp O(1)).

Khi khai báo như trên thì khi ta thêm các giá trị vào set thì các phần tử trong set sẽ có giá trị tăng dần.

Để thêm một giá trị và set s ta sử dụng hàm insert(). (Độ phức tạp O(logN). Khi thêm vào một phần tử thì size() của set sẽ tự tăng thêm một.

Lưu ý: trong một set sẽ không có hai phần tử cùng giá trị, nên khi bạn gọi hàm insert(x) mà trong set đó đã tồn tại giá trị x rồi thì set đó sẽ không thêm phần tử đó vào nữa.

	set <int> s;
	
	s.insert(1);  // s={1}
	
	s.insert(4);  // s={1,4}
	
	s.insert(2);  // s={1,2,4}
	
	s.insert(9);  // s={1,2,4,9}

Ta cũng có thể thay đổi các sắp xếp trong set bằng cách viết lại hàm , ví dụ muốn set theo giá trị giảm dần ta làm như sau:

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

struct cmp{
	bool operator() (int a,int b) {return a>b;}
}; 

int main() {

	set <int,cmp> s;

	s.insert(1);  // s={1}
	
	s.insert(4);  // s={4,1}
	
	s.insert(2);  // s={4,2,1}
	
	s.insert(9);  // s={9,4,2,1}
	
	for (set<int>:: iterator it = s.begin(); it != s.end(); it++){
		cout<< *it << " ";
	}

        return 0;

}

 

Hướng dẫn.

Ta sẽ thêm các phần tử của vector và một set, sau đó đưa ra số phần tử của set đó.

Code mẫu:

int differentNumbers(vector<int> inputVector )
{
	set<int> s;
	for (int i = 0; i < inputVector.size(); i++){
		s.insert(inputVector[i]);
	}
	return s.size();
}