Giúp mình với!Giúp mình với!python nha

1. Ý tưởng:

• Đọc dữ liệu đầu vào.
• Duyệt qua từng màu bi.
• Với mỗi màu, kiểm tra xem có cặp bi nào cùng màu và khoảng cách không quá k hay không.
• Nếu có, lưu lại màu đó.
• Tìm màu lớn nhất trong số các màu đã lưu.
• In ra kết quả.

2. Thuật toán:

• Đọc số nguyên n và k.
• Đọc mảng a chứa màu của từng viên bi.
• Khởi tạo một tập hợp bad_colors để lưu các màu gây "chướng mắt".
• Duyệt qua từng màu bi color từ 0 đến 10^6:
  • Khởi tạo một danh sách positions để lưu vị trí của các viên bi có màu color.
  • Duyệt qua mảng a:
    • Nếu a[i] bằng color, thêm i vào danh sách positions.
  • Duyệt qua danh sách positions:
    • Nếu có hai vị trí liên tiếp positions[j] và positions[j+1] mà positions[j+1] - positions[j] <= k, thêm color vào tập hợp bad_colors và thoát khỏi vòng lặp.
• Nếu bad_colors rỗng, in ra -1.
• Ngược lại, tìm màu lớn nhất trong bad_colors và in ra.

3. Cài đặt C++:

C++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

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

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

    set<int> bad_colors;
    for (int color = 0; color <= 1000000; ++color) {
        vector<int> positions;
        for (int i = 0; i < n; ++i) {
            if (a[i] == color) {
                positions.push_back(i);
            }
        }

        for (int j = 0; j < positions.size() - 1; ++j) {
            if (positions[j + 1] - positions[j] <= k) {
                bad_colors.insert(color);
                break;
            }
        }
    }

    if (bad_colors.empty()) {
        cout << -1 << endl;
    } else {
        cout << *bad_colors.rbegin() << endl;
    }

    return 0;
}

4. Độ phức tạp:

• Độ phức tạp thời gian: O(n * max_color) trong trường hợp xấu nhất, trong đó max_color là giá trị màu lớn nhất.
• Độ phức tạp không gian: O(n)

5. Tối ưu hóa:

• Để tối ưu hóa, ta có thể sử dụng map hoặc unordered_map để lưu vị trí của từng màu bi, giảm độ phức tạp thời gian xuống O(n).