+2

Tập hợp (Set) và một số ứng dụng

I. Giới thiệu chung

Với những ai đã và đang học lập trình, đặc biệt là lập trình thi đấu, thì những cấu trúc dữ liệu như set, map hay dictionary có lẽ là rất quen thuộc. Tên gọi của chúng có thể khác nhau ở các ngôn ngữ, nhưng tác dụng thì không hề thay đổi. Ứng dụng của chúng lớn đến mức, nhiều tài liệu khi hướng dẫn về lập trình cơ bản cũng đưa những cấu trúc dữ liệu này vào giảng dạy song song với mảng hay danh sách liên kết,...

Đúng như tên gọi của nó, tập hợp (set) là một cấu trúc dữ liệu dạng giống như mảng, lưu một danh sách các phần tử. Bản chất cấu trúc này được xây dựng dựa trên cấu trúc dữ liệu cây tìm kiếm nhị phân, nhưng nó đã phổ biến đến mức người ta quên đi cách cài đặt gốc của nó. Tuy nhiên, trong C++ và trong Python thì cấu trúc dữ liệu này sẽ có những sự khác biệt nhất định. Trong bài viết này, tôi sẽ giới thiệu tới các bạn về cách sử dụng chúng, cũng như minh họa một vài bài toán để bạn đọc hiểu hơn về ứng dụng của những cấu trúc này.

II. Sử dụng set trong C++

1. Khai báo

Trong C++, set là một associative container của thư viện Template chuẩn C++ (STL) (những container mà kiểm soát phần tử bằng giá trị chứ không phải bằng vị trí thì gọi là associative containers). Nó sử dụng để lưu trữ các phần tử có cùng kiểu dữ liệu, tuy nhiên các phần tử đó không được lặp lại.

Những phần tử được lưu trong set gọi là khóa. Trong set sử dụng sẵn phép so sánh mặc định là less, nghĩa là phần tử đứng trước sẽ nhỏ hơn phần tử đứng sau (theo phép so sánh). Khi sử dụng set, các bạn có thể viết lại hàm so sánh theo ý muốn của mình.

Để khai báo một set, ta sử dụng những cú pháp sau:

#include <set>

using namespace std;

// Khởi tạo một set rỗng.
set <{Kiểu_phần_tử}> {Tên_set};
// Tạo một set từ mảng khác. Có thể tạo ra set từ một đoạn của mảng.
set <{Kiểu_phần_tử}> {Tên_set}({Phạm_vi_trên_mảng});

Ví dụ, dưới đây ta tạo ra một set gồm toàn số nguyên từ một mảng cho trước (vector cũng sử dụng tương tự):

#include <set>

using namespace std;

main()
{
    int a[] = {1, 5, 2, 4, 3};
    set < int > integers(a, a + 5); // integers = {1, 2, 3, 4, 5}.
}

2. Các thao tác với set trong C++

Duyệt set

Các phần tử trong set không thể truy cập trực tiếp qua vị trí, mà buộc phải sử dụng vòng lặp để duyệt. Vì set là một container thuộc STL, nên các phần tử của nó có thể duyệt qua bằng iterator theo cú pháp:

// Khai báo biến lặp.
set < {Kiểu_phần_tử} > :: iterator {Tên_biến_lặp};

// Duyệt set.
for ({Biến_lặp} = {Địa_chỉ_đầu}; {Biến_lặp} != {Địa_chỉ_cuối}; ++{Biến_lặp})

Chẳng hạn, với một set kiểu số nguyên là integers\text{integers}, ta duyệt qua nó như sau:

set < int > :: iterator it;
for (it = integers.begin(); it != integers.end(); ++it)
    cout << *it << endl;

Với set integers={1,2,3,4,5};\text{integers} = \{1, 2, 3, 4, 5\}; đoạn chương trình trên sẽ có kết quả là:

1
2
3
4
5

Các hàm dựng sẵn

Container set đã xây dựng sẵn một số hàm để thao tác với set, cụ thể tôi trình bày ở bảng dưới đây. Để sử dụng hàm, ta dùng cú pháp: {Tên_set}.{Tên_hàm}. Coi rằng kích thước của set hiện tại là nn.

Tên hàm Tác dụng Độ phức tạp
insert(x) Thêm phần tử xx vào tập hợp, tự động sắp xếp lại O(log(n))O\big(\log(n)\big)
find(x) Trả về iterator trỏ tới phần tử xx trong tập hợp, nếu không tìm thấy thì trả về iterator end() O(log(n))O\big(\log(n)\big)
clear() Xóa toàn bộ tập hợp O(n)O(n)
erase(id) Xóa một phần tử idid trong tập hợp, có thể xóa theo khóa hoặc xóa theo iterator O(log(n))O\big(\log(n)\big)
size() Trả về kích thước hiện tại của tập hợp O(1)O(1)
empty() Trả về true nếu tập hợp rỗng, ngược lại trả về false O(1)O(1)
lower_bound(key) Trả về iterator trỏ tới phần tử nhỏ nhất có giá trị lớn hơn hoặc bằng khóa key\text{key} trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() O(log(n))O\big(\log(n)\big)
upper_bound(key) Trả về iterator trỏ tới phần tử nhỏ nhất có giá trị lớn hơn khóa keykey trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() O(log(n))O\big(\log(n)\big)
count(key) Trả về số lần xuất hiện của khóa key\text{key} trong tập hợp O(log(n))O\big(\log(n)\big)

Viết hàm so sánh cho set

Hàm so sánh của set có thể được viết riêng theo ý các bạn theo cú pháp sau:

struct cmp
{
    bool operator() ({Kiểu_phần_tử} x, {Kiểu_phần_tử} y) 
    {
        return {Quan_hệ_x_và_y};
    }
};

set <{Kiểu_phần_tử}, cmp> {Tên_set};

Trong hàm so sánh trên, phần tử xx sẽ đại diện cho phần tử đứng trước trong set, yy đại diện cho phần tử đứng sau. Nếu như hàm đó trả về kết quả true thì phần tử xx sẽ được xếp đứng trước phần tử yy trong set, ngược lại thì hai phần tử sẽ đổi chỗ cho nhau.

Ví dụ, muốn tạo một set lưu các số nguyên nhưng theo thứ tự giảm dần, ta làm như sau:

#include <set>

using namespace std;

struct cmp
{
    bool operator() (int x, int y)
    {
        return x > y;
    }
};

main()
{
    int arr[] = {1, 5, 2, 4, 3};
    set < int, cmp > integers(arr, arr + 5); // integers = {5, 4, 3, 2, 1}.
}

3. Các cấu trúc multiset và unordered_set

Ngoài ra, trong STL C++ còn xây dựng hai associative container khác gần giống với set:

  • multi_set: Cấu trúc này giống hệt như set nhưng cho phép lưu trữ nhiều phần tử có cùng khóa với nhau. Các bạn có thể tìm hiểu thêm về cấu trúc này tại <i>đây.</i>
  • unordered_set: Cấu trúc này cũng giống như set, nhưng các phần tử khi thêm vào sẽ không được sắp xếp theo thứ tự, nên các thao tác thêm và tìm kiếm phần tử chỉ tốn thời gian O(1)O(1). Nhưng cũng chính vì thế mà cấu trúc này sẽ không có các hàm tìm kiếm như lower_bound() và upper_bound(). Các bạn tìm hiểu thêm về cấu trúc này tại <i>đây.</i>

III. Sử dụng set trong Python

1. Khai báo

Trong ngôn ngữ Python, set có hơi khác biệt một chút so với C++. Vẫn là một danh sách lưu các phần tử phân biệt, tuy nhiên các phần tử lưu trong set của Python sẽ không có tính thứ tự (không được sắp xếp). Nhưng điều thuận tiện là nó có thể lưu trữ các phần tử với kiểu khác nhau, chẳng hạn như các phần tử kiểu chuỗi, số và list có thể được lưu cùng trong một set.

Để khai báo một set trong Python, ta sử dụng một số cú pháp sau:

# Khai báo set rỗng.
{Tên_set} = set()

# Khởi tạo set có sẵn các phần tử.
{Tên_set} = {{Phần_tử_thứ_nhất}, {Phần_tử_thứ_hai},...}

# Tạo set từ một list có sẵn.
{Tên_set} = set({Tên_list})

Lấy ví dụ:

set1 = set()
set2 = {"Vũ Quế Lâm", 1, ['a', 'b', 'c']}
set3 = set([1, 4, 2, 2, 5, 5])  # set3 = {1, 4, 2, 5}

Vậy có thể các bạn sẽ thắc mắc, nếu như ta muốn có một cấu trúc được sắp xếp giống như set của C++ trong Python thì phải làm sao? Câu trả lời là cấu trúc đó không tồn tại trong Python, vì bản chất cài đặt của set ở hai ngôn ngữ là khác nhau. Nhưng các bạn có thể cải tiến dictionary trong Python để thu được một cấu trúc tương tự, điều này sẽ được đề cập tới trong bài viết sau.

2. Các thao tác với set trong Python

Duyệt set

Các phần tử trong set của Python không có thứ tự nên không thể truy cập thông qua vị trí, mà buộc phải sử dụng vòng lặp:

for {Biến_đại_diện} in {Tên_set}:
    {Các_câu_lệnh}

Ví dụ:

set1 = {5, 6, 7, 4}
for item in set1:
    print(item)

Kết quả đoạn chương trình trên như sau:

5
6
7
4

Kiểm tra phần tử có ở trong set hay không

Sử dụng in hoặc not in để kiểm tra một phần tử có trong set hay không. Ví dụ:

myset = {10, 15, 19, 14}

print(10 in myset)
print(15 not in myset)

Kết quả:

True
False

Các hàm dựng sẵn

Tương tự như trong C++, set trong Python cũng đã được xây dựng sẵn một số hàm hỗ trợ, cụ thể như bảng dưới đây. Kí hiệu kích thước của set ss là s|s|:

Tên hàm Tác dụng Độ phức tạp
s.add(x) Thêm phần tử xx vào tập hợp O(1)O(1)
s.update({Các_phần_tử}) Thêm nhiều phần tử vào set O(m)O(m) - mm là số phần tử thêm vào
s.clear() Xóa toàn bộ set O(s)O\big(\|s\|\big)
s.pop() Xóa phần tử ở cuối set, tuy nhiên không nên sử dụng vì ta không biết phần tử ở cuối là phần tử nào O(1)O(1)
s.discard(x) Xóa phần tử xx trong set, nếu phần tử này không tồn tại thì cũng không báo lỗi O(1)O(1)
s.remove(x) Xóa phần tử xx trong set, nếu phần tử này không tồn tại thì sẽ báo lỗi O(1)O(1)
s1.union(s2) Kết hợp hai set s1s1 và s2s2 loại bỏ các phần tử trùng nhau của hai set - còn gọi là phép hợp O(s1+s2)O\big(\|s1\| + \|s2\|\big)
s1.intersection(s2) Trả về các phần tử chung giữa hai set - còn gọi là phép giao O(min(s1,s2))O\left(\text{min}\big(\|s1\|, \|s2\|\big)\right)
s1.different(s2) Trả về các phần tử chỉ thuộc một trong hai set - còn gọi là phép trừ O(s1)O\big(\|s1\|\big)

Ngoài ra trong set của Python còn khá nhiều hàm tích hợp khác, các bạn có thể xem kĩ hơn cả ví dụ minh họa tại <i>đây.</i>

IV. Một số bài toán minh họa

1. Bài toán 1

Đề bài

Tèo chuẩn bị tổ chức một bữa tiệc và anh ấy có nhiều thanh chocolate, trong đó có một số thanh chocolate cùng loại. Anh ấy muốn tặng chocolate cho bạn bè của mình một cách hoàn hảo, tức là mỗi người bạn của Tèo chỉ nhận được một thanh chocolate, và không có hai người bạn nào nhận được cùng một loại chocolate.

Hãy cho biết Tèo có thể tặng chocolate cho tối đa bao nhiêu người bạn?

Input:

  • Dòng đầu tiên chứa số nguyên nn chỉ số lượng thanh chocolate mà Tèo đang có.
  • Dòng thứ hai chứa nn số nguyên a1,a2,...,ana_1, a_2, ..., a_n với aia_i là loại của thanh chocolate thứ ii.

Ràng buộc:

  • 1n1061 \le n \le 10^6.
  • 0ai109;i:1in0 \le a_i \le 10^9; \forall i: 1 \le i \le n.

Output:

  • Số nguyên duy nhất là số lượng người bạn tối đa mà Tèo có thể phát chocolate.

Sample Input:

3
1 2 2

Sample Output:

2

Ý tưởng

Ý tưởng của bài toán này rất rõ ràng là đếm số lượng phần tử khác nhau trong dãy số ban đầu.

Ta có một vài cách để làm bài toán này:

  • Sắp xếp lại dãy số rồi duyệt lại cả dãy để xác định các phần tử phần biệt. Cách làm này hơi dài dòng và không đúng chủ đề nên tôi không đề cập.
  • Đếm phân phối các phần tử trong dãy số ban đầu. Cách làm này chỉ mất phức tạp O(max(ai))O\big(\text{max}(a_i)\big) - không phù hợp với ràng buộc của bài toán là ai109a_i \le 10^9.
  • Tạo ra một set từ dãy số ban đầu rồi đưa ra kích thước của set đó - cũng chính là số lượng phần tử phân biệt trong set. Cách làm này ngắn gọn và phù hợp nhất cho bài này.

Độ phức tạp chung của giải thuật sẽ là O(n.log(n))O\big(n.\log(n)\big).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

main()
{
    int n;
    cin >> n;

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

    set < int > unique_elements(a.begin(), a.end());

    cout << unique_elements.size();
}

Ngôn ngữ Python:

if __name__ == '__main__':
    n = int(input())
    a = [int(x) for x in input().split()]

    print(len(set(a)))

2. Bài toán 2

Đề bài

Hãy gọi một số là kk - tốt nếu nó chứa tất cả các chữ số không vượt quá k (0,...,k)k \ (0, ..., k). Bi có một số kk và một mảng AA chứa nn số. Tìm giúp Bi xem có bao nhiêu số đẹp kk trong AA (đếm từng số mỗi khi nó xuất hiện trong mảng aa).

Hãy xác định có bao nhiêu số kk - tốt trong dãy A?A?.

Input:

  • Dòng đầu tiên chứa nnkk tương ứng với đề bài.
  • nn dòng tiếp theo, mỗi dòng chứa một số aia_i - phần tử thứ ii của mảng A (1in)A \ (1 \le i \le n).

Ràng buộc:

  • 1n1051 \le n \le 10^5.
  • 0k90 \le k \le 9.
  • 1ai109;i:1in1 \le a_i \le 10^9; \forall i: 1 \le i \le n.

Output:

  • In ra số lượng số kk - tốt trong dãy aa.

Sample Input:

2 1
1
10

Sample Output:

1

Ý tưởng

Ứng với mỗi số ai,a_i, sử dụng đếm phân phối hoặc set để đếm các chữ số khác nhau của nó mà không vượt quá kk. Nếu số lượng chữ số khác nhau đó đúng bằng k+1k + 1 thì số aia_i là số kk - tốt, ngược lại thì không phải.

Sử dụng set tất nhiên sẽ cài đặt ngắn gọn hơn rất nhiều, nên tôi khuyến khích các bạn sử dụng cách này.

Độ phức tạp: O(n×log(k))O\big(n \times \log(k)\big).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

void enter(int &n, int &k, vector < string > &a)
{
    cin >> n >> k;

    a.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void solution(int n, int k, vector < string > &a)
{
    int res = 0;
    for (int i = 1; i <= n; ++i)
    {
        set < char > digits;
        for (char d: a[i])
        {
            if (d - '0' > k)
                continue;

            digits.insert(d);
        }

        res += (digits.size() == k + 1);
    }

    cout << res;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    vector < string > a;

    enter(n, k, a);
    solution(n, k, a);

    return 0;
}

Ngôn ngữ Python:

if __name__ == '__main__':
    n, k = map(int, input().split())

    res = 0
    for _ in range(n):
        a = input()

        digits = set()
        for d in a: 
            if int(d) > k: 
                digits.add(d)

        if len(digits) == k + 1:
            res += 1

    print(res)

V. Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.