โปรแกรมนับจำนวนรายการย่อยที่มีองค์ประกอบเฉพาะ k รายการใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนรายการย่อยที่ต้องการให้มี k หมายเลขที่ไม่ซ้ำกันในรายการย่อย

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 2, 3, 4] k =2 เอาต์พุตจะเป็น 3 เนื่องจากเรามีรายการย่อยเช่น [2, 2, 3], [2, 3], [3, 4].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน count() นี่จะใช้เวลา K
• สล็อต :=แผนที่ว่าง โดยค่าเริ่มต้น ค่าทั้งหมดจะเป็น 0
• i :=res :=0
• สำหรับแต่ละดัชนี j และค่า x nums ทำ
  • สล็อต[x] :=สล็อต[x] + 1
  • ในขณะที่ขนาดของช่อง> K ทำ
    • สล็อต[nums[i]] :=สล็อต[nums[i]] - 1
    • ถ้า slot[nums[i]] เหมือนกับ 0 แล้ว
      • ลบ slot[nums[i]]
    • ผม :=ผม + 1
  • res :=res + j - i + 1
• ผลตอบแทน
• จากวิธีหลัก ให้ทำดังนี้ -
• นับกลับ (k) - นับ (k - 1)

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

[2, 2, 3, 4], 2

ผลลัพธ์

3