โปรแกรมหาตัวเลขที่เกิดบ่อยที่สุดหลังเพิ่มค่า k ครั้งใน Python

สมมติว่ามีรายการตัวเลข nums และค่า k ดำเนินการเพิ่มค่าสมาชิกทีละ 1 ได้สูงสุด k ครั้ง ต้องการหาค่าที่เกิดบ่อยที่สุดที่ทำได้ หากมีหลายค่า ให้เลือกค่าน้อยที่สุด

ตัวอย่าง: nums = [1, 0, 0, 0, 8, 8, 8, 8], k = 8 ผลลัพธ์คือ 8 เพราะเพิ่ม 1 เป็น 8 (7 ครั้ง) และเพิ่ม 0 หนึ่งตัวเป็น 1 ได้ [8, 1, 0, 0, 8, 8, 8, 8]

ขั้นตอนการแก้ปัญหา

1. เรียง nums
2. low = 0, high = 0, dist = 0, best = 0, ret = -1
3. วนลูป بينما high < len(nums):
   • ถ้า high > 0 และ nums[high] != nums[high-1]: dist += (high - low) * (nums[high] - nums[high-1])
   • high += 1
   • วนลูป بينما dist > k:
     • dist -= nums[high-1] - nums[low]
     • low += 1
   • ถ้า high - low > best: best = high - low, ret = nums[high-1]
4. คืนค่า ret

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums, k):
        nums.sort()
        low, high = 0, 0
        dist = 0
        best = 0
        ret = -1
        while high < len(nums):
            if high > 0 and nums[high] != nums[high - 1]:
                dist += (high - low) * (nums[high] - nums[high - 1])
            high += 1
            while dist > k:
                dist -= nums[high - 1] - nums[low]
                low += 1
            if high - low > best:
                best = high - low
                ret = nums[high - 1]
        return ret

ob = Solution()
nums = [1, 0, 0, 0, 8, 8, 8, 8]
k = 8
print(ob.solve(nums, k))

อินพุต

[1, 0, 0, 0, 8, 8, 8, 8], 8

เอาต์พุต

8