Tính số mảng con liên tiếp có nhiều nhất k giá trị khác nhau.

Bài toán

Tìm số lượng mảng con liên tiếp có nhiều nhất k giá trị khác nhau trong mảng số nguyên đã cho.

Các thuật toán có thể giải bài toán

Có nhiều thuật toán có thể giải bài toán này, cụ thể:

1. Sliding Window: Thuật toán này duyệt qua từng mảng con có độ dài k trong mảng số nguyên đã cho, đếm số lượng giá trị khác nhau trong mảng con này, và cập nhật kết quả nếu số lượng giá trị khác nhau lớn hơn kết quả hiện tại. Độ phức tạp của thuật toán này là O(n), với n là số lượng phần tử trong mảng số nguyên đã cho.

2. Hash Table: Thuật toán này duyệt qua từng mảng con liên tiếp, sử dụng bảng băm để đếm số lượng giá trị khác nhau trong mỗi mảng con. Độ phức tạp của thuật toán này phụ thuộc vào số lượng giá trị khác nhau trong mỗi mảng con, tuy nhiên trong trường hợp tốt nhất khi mỗi mảng con đều có ít giá trị khác nhau, độ phức tạp của thuật toán là O(n*k), với k là số lượng giá trị khác nhau tối đa được phép trong mỗi mảng con.

3. Two Pointers: Thuật toán này sử dụng hai con trỏ trỏ tới vị trí bên trái và bên phải của một mảng con liên tiếp, duyệt qua các mảng con có độ dài k và đếm số lượng giá trị khác nhau trong mỗi mảng con. Độ phức tạp của thuật toán này là O(n*k), với k là số lượng giá trị khác nhau tối đa được phép trong mỗi mảng con.

4. Sort and Scan: Thuật toán này sắp xếp mảng số nguyên đã cho, sau đó duyệt qua các mảng con liên tiếp và đếm số lượng giá trị khác nhau trong mỗi mảng con. Độ phức tạp của thuật toán này là O(n*log n) do phải sắp xếp mảng trước khi duyệt qua các mảng con.

5. Trie: Thuật toán này xây dựng một cây Trie để lưu trữ tất cả các chuỗi con của mảng số nguyên đã cho, sau đó duyệt qua tất cả các nút trong cây Trie và đếm số lượng nút có độ sâu k và chứa ít nhất hai giá trị khác nhau. Độ phức tạp của thuật toán này là O(n^2) trong trường hợp xấu nhất, nếu mảng số nguyên đã cho là một dãy tăng dần hoặc giảm dần.

Tóm lại, trong số các thuật toán này, Sliding Window là thuật toán hiệu quả nhất với độ phức tạp là O(n).

Thuật toán Sliding Window

Thuật toán Sliding Window giải bài toán tìm số lượng mảng con liên tiếp có nhiều nhất k giá trị khác nhau trong mảng số nguyên đã cho. Thuật toán này sử dụng kỹ thuật trượt cửa sổ (sliding window) để duyệt qua các mảng con có độ dài k trong mảng số nguyên đã cho.

Bước 1: Khởi tạo hai biến left và right bằng 0, và một bộ đếm (counter) để đếm số lượng giá trị khác nhau trong mảng con hiện tại.

Bước 2: Duyệt qua mảng số nguyên đã cho bằng cách di chuyển biến right sang phải, sau đó cập nhật bộ đếm bằng cách tăng giá trị đếm của giá trị mới (nếu giá trị đó chưa xuất hiện trong mảng con) hoặc giảm giá trị đếm của giá trị bị loại bỏ khỏi mảng con (nếu đang di chuyển left sang phải).

Bước 3: Nếu số lượng giá trị khác nhau trong mảng con hiện tại vượt quá k, di chuyển biến left sang phải cho đến khi số lượng giá trị khác nhau trong mảng con hiện tại không vượt quá k.

Bước 4: Cập nhật kết quả nếu số lượng giá trị khác nhau trong mảng con hiện tại lớn hơn kết quả hiện tại.

Bước 5: Lặp lại các bước trên cho đến khi biến right di chuyển đến cuối mảng số nguyên.

Kết quả cuối cùng là số lượng mảng con liên tiếp có nhiều nhất k giá trị khác nhau trong mảng số nguyên đã cho.

Độ phức tạp của thuật toán Sliding Window là O(n), với n là số lượng phần tử trong mảng số nguyên đã cho, là độ phức tạp tốt nhất trong số các thuật toán được liệt kê để giải quyết bài toán này.

Cài đặt Thuật toán Sliding Window

Dưới đây là đoạn code Python cho thuật toán Sliding Window giải bài toán tìm số lượng mảng con liên tiếp có nhiều nhất k giá trị khác nhau trong mảng số nguyên đã cho:

def max_subarray(nums, k):
    left, right, count = 0, 0, 0
    counter = {}
    max_count = 0

    while right < len(nums):
        num = nums[right]
        if num not in counter or counter[num] == 0:
            count += 1
        counter[num] = counter.get(num, 0) + 1

        while count > k:
            num = nums[left]
            counter[num] -= 1
            if counter[num] == 0:
                count -= 1
            left += 1

        max_count = max(max_count, right - left + 1)
        right += 1

    return max_count

Hàm max_subarray nhận vào một mảng nums và một số nguyên k là số lượng giá trị khác nhau tối đa trong một mảng con liên tiếp. Biến left và right lần lượt là chỉ số trái và phải của cửa sổ đang xét, ban đầu cả hai bằng 0. Biến count là số lượng giá trị khác nhau hiện tại trong mảng con đang xét, ban đầu bằng 0. Biến counter là một từ điển dùng để đếm số lượng xuất hiện của từng giá trị trong mảng con đang xét.

Thuật toán sử dụng vòng lặp while để duyệt qua mảng nums từ vị trí left đến right. Trong mỗi vòng lặp, ta cập nhật giá trị của biến counter và count cho mảng con đang xét và tăng giá trị của biến right. Nếu count lớn hơn k, ta di chuyển biến left sang phải cho đến khi count không vượt quá k, và cập nhật giá trị của max_count nếu một mảng con mới có độ dài lớn hơn giá trị hiện tại của max_count.

Cuối cùng, hàm trả về giá trị của max_count là kết quả của bài toán.