Số lượng số nguyên duy nhất tối đa trong mảng con kích thước cho trước trong C++

Trong bài toán này, cho một mảng kích thước n và một số M. Nhiệm vụ là viết chương trình tìm số lượng số nguyên duy nhất tối đa trong mảng con có kích thước M.

Ví dụ minh họa

Đầu vào: mảng = {4, 1, 2, 1, 4, 3}, M = 4

Đầu ra: 4

Giải thích:

Tất cả các mảng con kích thước 4:
{4, 1, 2, 1} = 3 phần tử duy nhất
{1, 2, 1, 4} = 3 phần tử duy nhất
{2, 1, 4, 3} = 4 phần tử duy nhất

Phương pháp giải

Cách đơn giản: Sinh tất cả mảng con kích thước M và đếm phần tử duy nhất. Độ phức tạp O(n×M) - không hiệu quả.

Cách tối ưu - Kỹ thuật cửa sổ trượt (Sliding Window):

1. Tạo cửa sổ kích thước M đầu tiên, lưu các phần tử vào bảng băm (hash map)
2. Di chuyển cửa sổ: thêm phần tử mới, xóa phần tử cũ
3. Cập nhật số lượng phần tử duy nhất và theo dõi giá trị lớn nhất

Minh họa quá trình

Mảng = {4, 1, 2, 1, 4, 3}, Kích thước cửa sổ M = 4

Chương trình C++

#include<bits/stdc++.h> 
using namespace std; 

int maxUniqueElement(int a[], int N, int M) {
    map<int, int> hashMap;
    int uniqueCountWindow = 0;
    int uniqueCount = 0;
    
    // Khởi tạo cửa sổ đầu tiên
    for (int i = 0; i < M; i++) {
        if (hashMap.find(a[i]) == hashMap.end()) {
            hashMap.insert(make_pair(a[i], 1));
            uniqueCountWindow++;
        } else {
            hashMap[a[i]]++;
        }
    }
    uniqueCount = uniqueCountWindow;
    
    // Trượt cửa sổ
    for (int i = M; i < N; i++) {
        // Xóa phần tử cũ
        if (hashMap[a[i - M]] == 1) {
            hashMap.erase(a[i - M]);
            uniqueCountWindow--;
        } else {
            hashMap[a[i - M]]--;
        }
        
        // Thêm phần tử mới
        if (hashMap.find(a[i]) == hashMap.end()) {
            hashMap.insert(make_pair(a[i], 1));
            uniqueCountWindow++;
        } else {
            hashMap[a[i]]++;
        }
        
        uniqueCount = max(uniqueCount, uniqueCountWindow);
    }
    return uniqueCount;
}

int main() {
    int arr[] = {4, 1, 2, 1, 4, 3};
    int M = 4;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum number of unique elements in sub-array of size " 
         << M << " is " << maxUniqueElement(arr, N, M) << endl;
}

Kết quả

The maximum number of unique elements in sub-array of size 4 is 4

Độ phức tạp

• Thời gian: O(N)
• Không gian: O(M)