โปรแกรมค้นหารายการตัวเลขที่หน้าต่างขนาด K แต่ละหน้าต่างมีองค์ประกอบเฉพาะใน Python

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

ดังนั้น หากอินพุตเป็น nums =[2, 2, 3, 3, 4], k =2 ผลลัพธ์จะเป็น [1, 2, 1, 2] เช่นเดียวกับหน้าต่าง [2, 2] [2, 3], [3, 3] และ [3, 4].

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

• c :=สร้างพจนานุกรมขององค์ประกอบใน nums และความถี่ขององค์ประกอบ

• ans :=รายการใหม่

• สำหรับฉันในช่วง k ถึงขนาดของ nums ทำ

  • ขนาดแทรกของ c ที่ส่วนท้ายของ ans

  • c[nums[i]] :=c[nums[i]] + 1

  • c[nums[i - k]] :=c[nums[i - k]] - 1

  • ถ้า c[nums[i - k]] เท่ากับ 0 แล้ว

    • ลบ c[nums[i - k]]

• ขนาดแทรกของ c ที่ส่วนท้ายของ ans

• กลับมาอีกครั้ง

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

[1, 2, 1, 2]