Chương trình đếm số lượng danh sách con có chính xác k phần tử duy nhất trong Python

Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải tìm số lượng danh sách con được yêu cầu để có đúng k số duy nhất trong danh sách con.

Vì vậy, nếu đầu vào là nums =[2, 2, 3, 4] k =2, thì đầu ra sẽ là 3, vì chúng ta có các danh sách con như:[2, 2, 3], [2, 3], [3, 4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm đếm (). Điều này sẽ mất K
• slot:=một bản đồ trống, theo mặc định, tất cả các giá trị là 0
• i:=res:=0
• đối với mỗi chỉ số j và giá trị x nums, thực hiện
  • slot [x]:=slot [x] + 1
  • trong khi kích thước của vị trí> K, thực hiện
    • slot [nums [i]]:=slot [nums [i]] - 1
    • nếu vị trí [nums [i]] bằng 0, thì
      • loại bỏ vị trí [nums [i]]
    • i:=i + 1
  • res:=res + j - i + 1
• trả lại res
• Từ phương thức chính, hãy làm như sau -
• số lượng trả về (k) - số lượng (k - 1)

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from collections import Counter
class Solution:
   def solve(self, nums, k):
      def count(K):
         slot = Counter()
         i = res = 0
         for j, x in enumerate(nums):
            slot[x] += 1
            while len(slot) > K:
               slot[nums[i]] -= 1
               if slot[nums[i]] == 0:
                  del slot[nums[i]]
               i += 1
            res += j - i + 1
         return res
      return count(k) - count(k - 1)
ob = Solution()
nums = [2, 2, 3, 4]
k = 2
print(ob.solve(nums, k))

Đầu vào

[2, 2, 3, 4], 2

Đầu ra

3