Bài 18.3: Các bài toán sử dụng Set trong C++
Bài 18.3: Các bài toán sử dụng Set trong C++
Chào mừng các bạn quay trở lại với chuỗi bài viết về C++ của FullhouseDev!
Trong thế giới lập trình, chúng ta thường xuyên gặp phải các bài toán cần xử lý một tập hợp các phần tử mà có hai yêu cầu quan trọng:
- Các phần tử phải là duy nhất - không có bất kỳ phần tử nào bị lặp lại.
- Các phần tử cần được sắp xếp theo một thứ tự nào đó.
Nghe có vẻ quen thuộc phải không? Đó chính là khái niệm của một tập hợp trong toán học! Và may mắn thay, Thư viện Chuẩn C++ (Standard Library) đã cung cấp cho chúng ta một công cụ cực kỳ mạnh mẽ để xử lý những trường hợp này: đó chính là container set.
Bài viết này sẽ đi sâu vào cách set hoạt động, tại sao nó lại là lựa chọn tuyệt vời cho các bài toán tập hợp, và quan trọng hơn hết, chúng ta sẽ cùng nhau giải quyết một số bài toán thực tế bằng cách vận dụng sức mạnh của set.
set là gì? Tại sao nó lại hữu ích?
set là một container liên kết (associative container) trong C++. Điều đặc biệt về set là:
- Chứa các phần tử duy nhất: Khi bạn cố gắng thêm một phần tử đã tồn tại vào
set, thao tác thêm sẽ bị bỏ qua.setđảm bảo rằng mỗi giá trị chỉ xuất hiện một lần. - Các phần tử luôn được sắp xếp:
setduy trì các phần tử của nó theo thứ tự được sắp xếp (mặc định là tăng dần). Việc sắp xếp này được tự động thực hiện mỗi khi bạn thêm hoặc xóa phần tử. - Hiệu quả cho các thao tác tập hợp: Nhờ cấu trúc dữ liệu bên dưới (thường là cây tìm kiếm nhị phân cân bằng, ví dụ như cây Đỏ-Đen), các thao tác như thêm, xóa, và tìm kiếm một phần tử trong
setcó độ phức tạp thời gian là O(log N), trong đó N là số lượng phần tử trong set. Điều này cực kỳ hiệu quả so với việc tìm kiếm tuyến tính trong mảng hay vector (O(N)).
Với những đặc điểm này, set trở thành công cụ lý tưởng cho các bài toán yêu cầu quản lý dữ liệu duy nhất và có thứ tự.
Các Thao Tác Cơ Bản với set
Trước khi đi vào các bài toán, hãy cùng điểm qua một vài thao tác cơ bản nhất với set. Để sử dụng set, bạn cần bao gồm header <set>.
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(10);
s.insert(5);
s.insert(20);
s.insert(5);
cout << "Kich thuoc cua set: " << s.size() << endl;
cout << "Cac phan tu trong set: ";
for (int x : s) {
cout << x << " ";
}
cout << endl;
int giaTri = 10;
auto it = s.find(giaTri);
if (it != s.end()) {
cout << giaTri << " co ton tai trong set." << endl;
} else {
cout << giaTri << " khong ton tai trong set." << endl;
}
int giaTriKhac = 15;
if (s.count(giaTriKhac)) {
cout << giaTriKhac << " co ton tai trong set (dung count)." << endl;
} else {
cout << giaTriKhac << " khong ton tai trong set (dung count)." << endl;
}
s.erase(10);
cout << "Kich thuoc cua set sau khi xoa 10: " << s.size() << endl;
cout << "Cac phan tu trong set sau khi xoa: ";
for (int x : s) {
cout << x << " ";
}
cout << endl;
return 0;
}
Kich thuoc cua set: 3
Cac phan tu trong set: 5 10 20
10 co ton tai trong set.
15 khong ton tai trong set (dung count).
Kich thuoc cua set sau khi xoa 10: 2
Cac phan tu trong set sau khi xoa: 5 20Giải thích code:
Đoạn code trên minh họa các thao tác cơ bản: khai báo set<int>, thêm các số nguyên vào đó (chú ý số 5 được thêm hai lần nhưng chỉ xuất hiện một lần), lấy kích thước (size()), duyệt các phần tử (luôn theo thứ tự tăng dần), tìm kiếm một giá trị cụ thể (find() hoặc count()), và xóa một phần tử (erase()).
Áp Dụng set vào Bài Toán Thực Tế
Giờ là lúc vận dụng set để giải quyết một số bài toán phổ biến.
Ví dụ 1: Đếm số lượng phần tử duy nhất trong một mảng/vector.
Bài toán: Cho một tập hợp các số (có thể có số lặp lại) dưới dạng mảng hoặc vector. Hãy tìm số lượng các phần tử duy nhất trong tập hợp đó.
Tại sao dùng set?: Đây là bài toán kinh điển cho set. Bằng cách đơn giản là đưa tất cả các phần tử từ mảng/vector vào một set, set sẽ tự động loại bỏ các phần tử trùng lặp. Kích thước cuối cùng của set chính là số lượng phần tử duy nhất.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
vector<int> a = {1, 2, 5, 3, 2, 4, 1, 5, 5, 3, 10, 8, 8, 12};
set<int> s(a.begin(), a.end());
cout << "Vector ban dau: ";
for(int x : a) cout << x << " ";
cout << endl;
cout << "So luong phan tu duy nhat: " << s.size() << endl;
cout << "Cac phan tu duy nhat (da sap xep): ";
for (int x : s) {
cout << x << " ";
}
cout << endl;
return 0;
}
Vector ban dau: 1 2 5 3 2 4 1 5 5 3 10 8 8 12
So luong phan tu duy nhat: 8
Cac phan tu duy nhat (da sap xep): 1 2 3 4 5 8 10 12Giải thích code:
Chúng ta tạo một vector numbers với các số có thể lặp lại. Sau đó, tạo một set<int> có tên uniqueNumbers. Vòng lặp for duyệt qua vector và thêm từng phần tử vào set. Do tính chất của set, các số lặp lại sẽ không được thêm vào lần thứ hai. Cuối cùng, uniqueNumbers.size() cho chúng ta số lượng phần tử duy nhất. Bạn cũng thấy các phần tử khi in ra từ set đã được tự động sắp xếp. Cách khởi tạo set trực tiếp từ range của vector (set<int> uniqueNumbers(numbers.begin(), numbers.end());) là một cách viết gọn và hiệu quả hơn.
Ví dụ 2: Kiểm tra sự tồn tại của một phần tử một cách hiệu quả.
Bài toán: Cho một tập dữ liệu lớn và một giá trị cụ thể. Hãy kiểm tra xem giá trị đó có tồn tại trong tập dữ liệu hay không một cách nhanh chóng.
Tại sao dùng set?: Nếu bạn lưu trữ tập dữ liệu trong một vector hoặc mảng thông thường và thực hiện tìm kiếm tuyến tính, độ phức tạp sẽ là O(N) (trong trường hợp xấu nhất). Tuy nhiên, nếu bạn lưu trữ dữ liệu trong set, thao tác tìm kiếm (find() hoặc count()) chỉ mất O(log N). Điều này tạo ra sự khác biệt lớn khi làm việc với tập dữ liệu có kích thước hàng ngàn, hàng triệu phần tử.
#include <iostream>
#include <vector>
#include <set>
#include <chrono>
using namespace std;
int main() {
vector<int> v;
for (int i = 0; i < 100000; ++i) {
v.push_back(i * 2);
}
v.push_back(199999);
v.push_back(55555);
set<int> s(v.begin(), v.end());
int gt1 = 50000;
int gt2 = 50001;
int gt3 = 199999;
auto start = chrono::high_resolution_clock::now();
if (s.count(gt1)) {
cout << gt1 << " co ton tai trong set." << endl;
}
if (!s.count(gt2)) {
cout << gt2 << " khong ton tai trong set." << endl;
}
if (s.count(gt3)) {
cout << gt3 << " co ton tai trong set." << endl;
}
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> thoiGian = end - start;
cout << "Thoi gian tim kiem dung set: " << thoiGian.count() << " giay." << endl;
return 0;
}
50000 co ton tai trong set.
50001 khong ton tai trong set.
199999 co ton tai trong set.
Thoi gian tim kiem dung set: 0.00000X giay. (Số này có thể khác nhau tùy hệ thống và thời điểm chạy)Giải thích code:
Chúng ta tạo một vector largeData với 100,000 phần tử. Việc chuyển nó sang set (dataSet) mất một ít thời gian ban đầu (O(N log N)), nhưng sau đó, việc kiểm tra sự tồn tại của các giá trị (dataSet.count(...)) được thực hiện cực kỳ nhanh chóng với độ phức tạp O(log N). Với dữ liệu lớn, sự khác biệt về thời gian thực thi giữa tìm kiếm O(log N) và O(N) là rất đáng kể.
Ví dụ 3: Tìm hợp (Union) của hai tập hợp.
Bài toán: Cho hai tập hợp A và B. Tìm tập hợp chứa tất cả các phần tử có trong A hoặc B (hoặc cả hai), mà không có phần tử nào bị lặp lại.
Tại sao dùng set?: set tự nhiên biểu diễn một tập hợp toán học. Để tìm hợp của hai tập hợp, bạn chỉ cần đưa tất cả các phần tử từ cả hai tập hợp vào một set mới. set sẽ tự động loại bỏ các phần tử trùng lặp, và kết quả chính là tập hợp hợp.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int main() {
vector<int> v1 = {1, 3, 5, 7, 9, 11};
vector<int> v2 = {2, 3, 4, 5, 6, 7, 8};
set<int> sHop;
for (int x : v1) {
sHop.insert(x);
}
for (int x : v2) {
sHop.insert(x);
}
cout << "Vector 1: "; for(int n : v1) cout << n << " "; cout << endl;
cout << "Vector 2: "; for(int n : v2) cout << n << " "; cout << endl;
cout << "Hop cua hai tap hop (dung set insert): ";
for (int x : sHop) {
cout << x << " ";
}
cout << endl;
set<int> s1(v1.begin(), v1.end());
set<int> s2(v2.begin(), v2.end());
set<int> sHopAlt;
set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
inserter(sHopAlt, sHopAlt.begin()));
cout << "Hop (dung set_union): ";
for (int x : sHopAlt) {
cout << x << " ";
}
cout << endl;
return 0;
}
Vector 1: 1 3 5 7 9 11
Vector 2: 2 3 4 5 6 7 8
Hop cua hai tap hop (dung set insert): 1 2 3 4 5 6 7 8 9 11
Hop (dung set_union): 1 2 3 4 5 6 7 8 9 11Giải thích code:
Cách đơn giản nhất là tạo một set mới và thêm tất cả phần tử từ cả hai vector vào đó. Set tự động xử lý việc trùng lặp và sắp xếp. set_union là một thuật toán trong <algorithm> có thể thực hiện phép hợp trên hai dãy đã được sắp xếp. Vì set luôn giữ các phần tử đã sắp xếp, chúng ta có thể dễ dàng dùng iterator của set với set_union. inserter là một adapter iterator giúp thuật toán set_union thêm các phần tử vào set kết quả thay vì ghi đè lên một vùng nhớ có sẵn.
Ví dụ 4: Tìm giao (Intersection) của hai tập hợp.
Bài toán: Cho hai tập hợp A và B. Tìm tập hợp chứa tất cả các phần tử chỉ có trong cả hai tập hợp A và B.
Tại sao dùng set?: Tương tự phép hợp, chúng ta có thể tận dụng khả năng tìm kiếm nhanh của set. Chuyển một trong hai tập hợp sang dạng set để việc tìm kiếm hiệu quả (O(log N)). Sau đó, duyệt qua tập hợp còn lại và kiểm tra xem mỗi phần tử có tồn tại trong set kia không. Nếu có, đó là phần tử thuộc giao, và chúng ta thêm nó vào một set kết quả.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int main() {
vector<int> v1 = {1, 3, 5, 7, 9};
vector<int> v2 = {3, 6, 9, 12, 15};
set<int> s1(v1.begin(), v1.end());
set<int> sGiao;
cout << "Vector 1: "; for(int n : v1) cout << n << " "; cout << endl;
cout << "Vector 2: "; for(int n : v2) cout << n << " "; cout << endl;
for (int x : v2) {
if (s1.count(x)) {
sGiao.insert(x);
}
}
cout << "Giao cua hai tap hop (dung set count): ";
for (int x : sGiao) {
cout << x << " ";
}
cout << endl;
set<int> s2(v2.begin(), v2.end());
set<int> sGiaoAlt;
set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
inserter(sGiaoAlt, sGiaoAlt.begin()));
cout << "Giao (dung set_intersection): ";
for (int x : sGiaoAlt) {
cout << x << " ";
}
cout << endl;
return 0;
}
Vector 1: 1 3 5 7 9
Vector 2: 3 6 9 12 15
Giao cua hai tap hop (dung set count): 3 9
Giao (dung set_intersection): 3 9Giải thích code:
Chúng ta chuyển vec1 thành set1 để có thể tìm kiếm nhanh. Sau đó, duyệt qua vec2. Đối với mỗi phần tử trong vec2, chúng ta dùng set1.count(num) để kiểm tra xem nó có tồn tại trong set1 không. Nếu có, chúng ta biết rằng phần tử này có mặt trong cả hai tập hợp, nên thêm nó vào intersectionSet. intersectionSet cũng là một set nên nó tự động đảm bảo các phần tử giao là duy nhất và được sắp xếp. Tương tự phép hợp, bạn có thể sử dụng thuật toán set_intersection trong <algorithm> với các range đã được sắp xếp.
Ví dụ 5: Sắp xếp và loại bỏ trùng lặp một dãy.
Bài toán: Cho một dãy các phần tử. Cần thu được một dãy mới chỉ chứa các phần tử duy nhất từ dãy ban đầu, và các phần tử này phải được sắp xếp.
Tại sao dùng set?: Đây chính xác là những gì set làm! Khi bạn đưa các phần tử vào set, nó sẽ tự động sắp xếp chúng và chỉ giữ lại các bản sao duy nhất.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {10, 4, 8, 4, 12, 6, 8, 10, 2, 10, 6};
cout << "Vector ban dau: ";
for(int n : v) cout << n << " ";
cout << endl;
set<int> s(v.begin(), v.end());
cout << "Cac phan tu duy nhat va da sap xep (tu set): ";
for (int x : s) {
cout << x << " ";
}
cout << endl;
vector<int> ketQua(s.begin(), s.end());
cout << "Ket qua trong vector (duy nhat, da sap xep): ";
for (int x : ketQua) {
cout << x << " ";
}
cout << endl;
return 0;
}
Vector ban dau: 10 4 8 4 12 6 8 10 2 10 6
Cac phan tu duy nhat va da sap xep (tu set): 2 4 6 8 10 12
Ket qua trong vector (duy nhat, da sap xep): 2 4 6 8 10 12Giải thích code:
Chúng ta khởi tạo set trực tiếp từ range của vector data. Thao tác này hiệu quả và gọn gàng. Set uniqueSortedData lúc này chứa các phần tử duy nhất từ data, và chúng đã được sắp xếp. Việc duyệt qua set sẽ cho các phần tử theo thứ tự tăng dần. Nếu cần kết quả cuối cùng dưới dạng vector, bạn có thể dễ dàng copy các phần tử từ set sang vector bằng cách sử dụng range constructor của vector (vector<int> resultVector(uniqueSortedData.begin(), uniqueSortedData.end());).
Các Biến Thể Của Set: Khi nào cần dùng?
Ngoài set "truyền thống", C++ còn cung cấp các biến thể khác trong Standard Library:
multiset: Giống nhưset, nhưng cho phép chứa các phần tử trùng lặp. Các phần tử vẫn được sắp xếp. Thao tác thêm, xóa, tìm kiếm cũng có độ phức tạp O(log N).unordered_set: Chứa các phần tử duy nhất, nhưng không đảm bảo thứ tự của các phần tử. Thay vì sử dụng cây tìm kiếm nhị phân,unordered_setsử dụng bảng băm (hash table). Nhờ đó, các thao tác thêm, xóa, tìm kiếm có độ phức tạp trung bình là O(1) (rất nhanh!), nhưng trong trường hợp xấu nhất (va chạm băm nhiều) có thể lên tới O(N). Bạn cần bao gồm header<unordered_set>. Sử dụngunordered_setkhi bạn chỉ cần tính duy nhất và tốc độ tìm kiếm là ưu tiên hàng đầu, còn thứ tự không quan trọng.
Hiểu rõ sự khác biệt giữa set, multiset, và unordered_set sẽ giúp bạn lựa chọn container phù hợp và hiệu quả nhất cho từng bài toán cụ thể.
Comments