Chương trình đếm số phần tử khác nhau trong mỗi cửa sổ kích thước K trong Python

Cho danh sách và số . Trả về danh sách số lượng phần tử khác nhau trong mỗi cửa sổ trượt kích thước .

Ví dụ: , → [1, 2, 1, 2] (cửa sổ: [2,2], [2,3], [3,3], [3,4]).

Giải thuật (Cửa sổ trượt + Counter)

1. Khởi tạo cho cửa sổ đầu.
2. Duyệt từ đến :
   • Thêm vào kết quả.
   • Thêm vào .
   • Giảm trong , xóa nếu về 0.
3. Thêm cho cửa sổ cuối.
4. Trả về kết quả.

Ví dụ minh họa

from collections import Counter

class Solution:
    def solve(self, nums, k):
        c = Counter()
        for i in range(k):
            c[nums[i]] += 1
        ans = []
        for i in range(k, len(nums)):
            ans.append(len(c))
            c[nums[i]] += 1
            c[nums[i - k]] -= 1
            if c[nums[i - k]] == 0:
                del c[nums[i - k]]
        ans.append(len(c))
        return ans

ob = Solution()
nums = [2, 2, 3, 3, 4]
print(ob.solve(nums, 2))  # Output: [1, 2, 1, 2]

Đầu vào

[2, 2, 3, 3, 4], 2

Đầu ra

[1, 2, 1, 2]