Kỹ thuật mảng đánh dấu, đếm phân phối

Đỗ Thị Hồng Ngát 13/07/2024
13
Th7

Kỹ thuật mảng đánh dấu, đếm phân phối

Kỹ thuật đếm phân phối và mảng đánh dấu là những phương pháp hữu ích trong lập trình, thường được sử dụng để giải quyết các bài toán liên quan đến tần suất và sự xuất hiện của các phần tử.

1. Mảng đánh dấu (Flag Array)

Mảng đánh dấu là một kỹ thuật đơn giản nhưng hiệu quả để theo dõi sự xuất hiện hoặc trạng thái của các phần tử trong một tập hợp. Mỗi phần tử trong tập hợp được ánh xạ tới một vị trí trong mảng đánh dấu, và giá trị tại vị trí đó cho biết phần tử có xuất hiện hay không (hoặc trạng thái của phần tử).

Nguyên lý hoạt động

  • Khởi tạo mảng đánh dấu: Tạo một mảng đánh dấu với kích thước bằng số phần tử tối đa cần theo dõi.
  • Cập nhật mảng đánh dấu: Duyệt qua các phần tử và cập nhật mảng đánh dấu tương ứng.

Bài toán 1. CHỮ SỐ BỊ THIẾU

Mô tả đề bài
Cho một mảng \(A\) chứa các số nguyên dương từ \(1\)đến \(N\), nhưng có một số số bị thiếu. Hãy tìm tất cả các số bị thiếu trong dãy \(A\).
Giải pháp sử dụng mảng đánh dấu

  • Tạo một mảng đánh dấu \(flags\) với kích thước \(N + 1\), khởi tạo tất cả các giá trị ban đầu là False.
  • Duyệt qua mảng đầu vào và đánh dấu các vị trí tương ứng trong mảng \(flags\) là True.
  • Cuối cùng, duyệt qua mảng \(flags\) để tìm các vị trí nào vẫn còn False, đó là các số bị thiếu trong dãy.

Bài toán 2. ĐẾM KÝ TỰ (CPBCSTR)

Đây là một bài tập luyện tập trong sách Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài
Cho xâu \(𝑆\). Hãy đếm xem xâu \(𝑆\) có bao kí tự chữ cái, chữ số khác nhau (chữ cái in thường, in hoa là không phân biệt).
INPUT

Abcdea 96hjab

OUTPUT

9

Giải pháp sử dụng mảng đánh dấu

  • Tạo một mảng đánh dấu chữ cái \(letters\) với kích thước \(26\), khởi tạo tất cả các giá trị ban đầu là False. Mỗi phần tử trong mảng này sẽ tương ứng với sự xuất hiện của \(26\) ký tự chữ cái. Phần tử ở vị trí \(0\) sẽ đại diện cho chữ cái \(a/A\), phần tử ở vị trí \(1\) đại điện cho chữ cái \(b/B\)…Phần tử ở vị trí 25 sẽ đại điện cho chữ cái \(z/Z\).
  • Tạo một mảng đánh dấu chữ cái \(numbers\) với kích thước \(10\), khởi tạo tất cả các giá trị ban đầu là False. Mỗi phần tử trong mảng này sẽ tương ứng với sự xuất hiện của \(10\) ký tự chữ số. Phần tử ở vị trí \(0\) sẽ đại diện cho chữ số \(0\), phần tử ở vị trí \(1\) đại điện cho chữ số \(1\)…Phần tử ở vị trí 9 sẽ đại điện cho chữ số \(9\).
  • Duyệt qua toàn bộ ký tự trong xâu ban đầu, xét ký tự thứ \(i\) của xâu \(S\):
    • Nếu đó là ký tự chữ cái, ta thực hiện tìm vị trí của chữ cái đó trong mảng \(letters\) bằng cách sử dụng bảng mã ASCCI (gọi là \(pos\)). Nếu chữ cái đó là chữ hoa, \(pos = int(S[i])-65 \) trong C++ hoặc \(pos = ord(s[i])-65\) trong Python. Tương tự, nếu chữ cái đó là chữ thường, \(pos = int(S[i])-97 \) trong C++ hoặc \(pos = ord(S[i])-97\) trong Python
    • Nếu đó là ký tự chữ số, ta thực hiện tìm vị trí của chữ số đó trong mảng \(numbers\) bằng cách sử dụng bảng mã ASCCI (gọi là \(pos\)). \(pos = int(S[i])-48 \) trong C++ hoặc \(pos = ord(S[i])-48\) trong Python.
    • Đánh dấu lại vị trí \(pos\) tìm được ở các mảng tương ứng.
  • Cuối cùng, duyệt qua hai mảng \(letters\) và \(numbers\) và đếm số lượng vị trí có giá trị bằng True, đó là số lượng ký tự chữ cái, chữ số khác nhau trong xâu \(S\).

Code mẫu C++

#include <iostream>
    #include <string>

    using namespace std;
    
    int main() {
        string S;
        getline(cin, S);  // Nhập xâu S
    
        // Tạo mảng đánh dấu cho chữ cái và chữ số
        bool letters[26] = {false};
        bool numbers[10] = {false};
    
        // Duyệt qua từng ký tự trong xâu S sử dụng chỉ số
        for (int i = 0; i < S.length(); i++) {
            char ch = S[i];
            // Kiểm tra chữ cái chữ thường
            if (ch >= 97 && ch <= 122) { // 'a' đến 'z' trong ASCII
                int pos = ch - 97;
                letters[pos] = true; // Đánh dấu chữ cái
            }
            // Kiểm tra chữ cái chữ hoa
            else if (ch >= 65 && ch <= 90) { // 'A' đến 'Z' trong ASCII
                int pos = ch - 65;
                letters[pos] = true; // Đánh dấu chữ cái
            }
            // Kiểm tra chữ số
            else if (ch >= 48 && ch <= 57) { // '0' đến '9' trong ASCII
                int pos = ch - 48;
                numbers[pos] = true; // Đánh dấu chữ số
            }
        }
    
        // Đếm số lượng phần tử đã được đánh dấu trong mỗi mảng
        int num_letters = 0;
        for (int i = 0; i < 26; i++) {
            if (letters[i]) {
                num_letters++;
            }
        }
    
        int num_numbers = 0;
        for (int i = 0; i < 10; i++) {
            if (numbers[i]) {
                num_numbers++;
            }
        }
    
        // In ra kết quả
        cout << num_letters + num_numbers << endl;
    
        return 0;
    }

Code mẫu Python

# Đọc xâu S
    S = input()

    # Tạo mảng đánh dấu cho chữ cái và chữ số
    letters = [False] * 26
    numbers = [False] * 10
    
    # Duyệt qua từng ký tự trong xâu S
    for i in range(len(S)):
        ch = S[i]
        # Kiểm tra chữ cái chữ thường
        if ord(ch) >= 97 and ord(ch) <= 122:  # 'a' đến 'z' trong ASCII
            pos = ord(ch) - 97
            letters[pos] = True  # Đánh dấu chữ cái
        # Kiểm tra chữ cái chữ hoa
        elif ord(ch) >= 65 and ord(ch) <= 90:  # 'A' đến 'Z' trong ASCII
            pos = ord(ch) - 65
            letters[pos] = True  # Đánh dấu chữ cái
        # Kiểm tra chữ số
        elif ord(ch) >= 48 and ord(ch) <= 57:  # '0' đến '9' trong ASCII
            pos = ord(ch) - 48
            numbers[pos] = True  # Đánh dấu chữ số
    
    # Đếm số lượng phần tử đã được đánh dấu trong mỗi mảng
    num_letters = sum(letters)
    num_numbers = sum(numbers)
    
    # In ra kết quả
    print(num_letters + num_numbers)

2. Kỹ thuật đếm phân phối (Counting Distribution Technique)

Kỹ thuật đếm phân phối (còn gọi là Counting Sort) là một thuật toán sắp xếp không dựa trên so sánh, thường được sử dụng khi các giá trị đầu vào nằm trong một phạm vi nhỏ. Thường được sử dụng để giải quyết các bài toán liên quan đến tần suất và sự xuất hiện của các phần tử.
Tương tự với mảng đánh dấu, đếm phân phối thay vì các phần tử chỉ lưu hai giá trị

Bài toán: TẦN SỐ #1 (CPBTANSO1)

Đây là một bài tập luyện tập trong sách Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài
Cho dãy \(𝑎\) gồm \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\). Đưa ra số lần xuất hiện của các giá trị trong dãy.
Biết \(a_i \le 10^6 \)

Sử dụng mảng đếm phân phối

  • Khởi tạo mảng frequency có kích thước bằng giá trị lớn nhất có thể ở trong mảng \(a\), là \(10^6+1\). Ban đầu các phần tử trong mảng đều có giá trị bằng \(0\). Mảng này có ý nghĩa là \(frequency[x]\) là số lần xuất hiện của số có giá trị \(x\)
  • Xét từng phần tử trong mảng \(a\), tăng số lần xuất hiện của giá trị \(a[i]\) lên \(1\). Nghĩa là \(frequency[a[i]] += 1\).
  • Muốn in ra tần suất xuất hiện của từng giá trị, tiến hành xét từng phần tử \(a[i]\), nếu \(frequency[a[i]]==0\) thì đưa ra \(a[i]\) và \(frequency[a[i]]\). Đồng thời, gán \(frequency[a[i]]=0\) để những phần tử có cùng giá trị phía sau sẽ không in lại nữa.

Code mẫu C++

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
    
        // Tạo mảng đếm phân phối để đếm số lần xuất hiện của các giá trị
        vector<int> frequency(1000001, 0);
        vector<int> a(n);
    
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            frequency[a[i]]++;
        }
    
        // Đưa ra số lần xuất hiện của các giá trị
        for (int i = 0; i < n; ++i) {
            if (frequency[a[i]] != 0) {
                cout << a[i] << " " << frequency[a[i]] << endl;
                frequency[a[i]] = 0; // Đảm bảo mỗi giá trị chỉ được in ra một lần
            }
        }
    
        return 0;
    }

Code mẫu Python

n = int(input())

    # Tạo mảng đánh dấu để đếm số lần xuất hiện của các giá trị
    frequency = [0] * (10**6 + 1)
    a = []
    
    # Nhập các phần tử của dãy
    for _ in range(n):
        num = int(input())
        a.append(num)
        frequency[num] += 1
    
    # Đưa ra số lần xuất hiện của các giá trị
    for num in a:
        if frequency[num] != 0:
            print(num, frequency[num])
            frequency[num] = 0  # Đảm bảo mỗi giá trị chỉ được in ra một lần

3. Kết luận

Đánh giá kỹ thuật đếm phân phối

  • Đơn giản, dễ cài đặt.
  • Chỉ xử lý được với các bộ dữ liệu có phạm vi nhỏ, giá trị lớn nhất của các phần tử cần đánh dấu phải nằm trong phạm vi từ \(0\) đến \(10^6\) – \(10^7\).
  • Độ phức tạp: \(O(n)\) cho sự chuẩn bị, \(O(1)\) để kiểm tra.

Hướng cải tiến
Để giải quyết những bộ dữ liệu có phạm vi lớn hơn, hay bộ dữ liệu có số âm, bộ dữ liệu không phải số, cần dùng kỹ thuật ánh xạ, hoặc sử dụng cấu trúc dữ liệu map trong thư viện STL. Tham khảo thêm tại bài viết này: C++ STL: Tổng hợp CTDL

Để luyện tập thêm các bài tập về Xử lý mảng trong sách Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay và chấm bài online tại http://oj.codedream.edu.vn

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *