Cấu trúc dữ liệu kiểu tập hợp và ứng dụng

Cấu trúc dữ liệu kiểu tập hợp và ứng dụng

1. SET (tập hợp) là gì?

Chắc bạn đã biết rất nhiều cấu trúc dữ liệu cơ bản rồi. Cấu trúc dữ liệu đơn giản nhất mà mình nghĩ ai cũng biết đó là mảng (array)

Sau đó đa phần sẽ biết tới queue và stack. Còn riêng bài này mình sẽ giới thiệu về set

Set cũng là 1 cấu trúc dữ liệu để lưu một danh sách các phần tử cùng kiểu dữ liệu, trong đó các phần tử không được trùng nhau. Ví dụ như array có thể có các phần tử trùng nhau như {1, 2, 1, 1, 2} nhưng set thì chỉ chứa các phần tử khác nhau {1, 2}

Tại sao set lại chỉ chứa các phần tử khác nhau, ấy là vì khi insert mỗi phần tử x vào trong set, set sẽ kiểm tra và chỉ thêm phần tử đó khi x không có trong set.

Đối với C++, class set và các phương thức liên quan, bạn có thể tìm hiểu tại đây, với Java thì tại đây

Như đã nói ở trên, khi chèn/ thêm mới 1 phần tử vào trong set, thì set sẽ kiểm tra xem có phần tử trong tập hợp chưa? Bài toán trong việc cài đặt set quy về việc làm sao trả lời câu hỏi phần tử có trong tập hợp ban đầu hay chưa?

Bài toán đặt ra là nếu có 1 dãy các phần tử a1, a2, ... an, hãy trả lời câu hỏi có tồn tại x trong dãy này không. Thông thường nếu các bạn duyệt từ 1 tới n để kiểm tra, độ phức tạp sẽ là O(n). Tuy nhiên nếu dãy a1->an là dãy sắp xếp tăng dần, thì việc tìm kiếm x có trong dãy hay không bằng phương pháp tìm kiếm nhị phân sẽ có độ phức tạp là o(logn). Đó cũng chính là 1 trong các phương pháp cơ bản để cài đặt.

Đối với C++, có 2 lớp cài đặt/biểu diễn set hay được dùng là set và unordered_set. Trong java thì có 3 cách cài đặt set là HashSet, TreeSet và LinkedHashSet. Ngắn gọn thì set của C++ và treeset của Java thì cài đặt dựa trên tree, và dùng tư tưởng tìm kiếm nhị phân, trong khi unordered_set của C++ và hashset của java thì cài đặt dựa trên bảng băm. Mỗi lớp sẽ có sự khác nhau về performance trong từng trường hợp, hãy đọc link này hay link này để biết thêm chi tiết.

2. Bài toán ứng dụng

Do set chỉ chứa các phần tử không trùng nhau, nên bạn có thể sử dụng cấu trúc dữ liệu này cho 1 số bài toán liên quan tới tập hợp như các bài toán sau:

  1. Cho dãy n phần tử. Hãy đếm số phần tử khác nhau trong mảng bài này nếu không dùng set, bạn có thể đánh dấu mỗi phần tử trong mảng có hay chưa với dữ liệu nhỏ. Nhưng nếu giá trị của các phần tử rất lớn (Ví dụ từ 1 tới 10^9, bạn sẽ làm cách nào). Bạn có thể tự lưu 1 mảng chứa các phần tử không trùng nhau, sau đó mỗi khi gặp phần tử mới thì kiểm tra trùng hay không và thêm vào mảng. Cách làm như vậy vừa tốn công sức cài đặt, trong khi nếu không dùng tìm kiếm nhị phân thì thời gian cực chậm. Đoạn mã sau đây sẽ cho các bạn hiểu rõ hơn (mình demo bằng C++ nhé):
    set<int> s;
    for (int i=0; i<n; i++)
    insert(a[i]);
    return s.size();
  2. Cho danh sách chứa thời gian quẹt thẻ của nhân viên trong ngày. Hãy kiểm tra xem có bao nhiêu người khác nhau đi làm trước 9h sáng. Cũng giống bài trên, chỉ khác là bài này bạn dùng tên nhân viên nếu tên nhân viên không trùng nhau (hoặc mã nhân viên) để đưa vào tập hợp. Mã giả như thế này nhé:
    set<string> s;
    for (int i=0; i<n; i++)
      if (a[i].time.hours <= 9) s.insert(a[i].name);
    return s.size();

3. Tổng kết

Mình đã giới thiệu sơ qua về cấu trúc dữ liệu kiểu set và vài ví dụ trong việc sử dụng set. Trên CodeLearn có nhiều bài ứng dụng cấu trúc dữ liệu này. 

Hy vọng các bạn gặp bài tương tự trong thực tế hãy biết và sử dụng cấu trúc dữ liệu này để tăng năng suất và hiệu quả của code.