Chương trình tìm số xuất hiện nhiều nhất sau k lần tăng trong Python

Mô tả bài toán

Cho danh sách nums và số k. Mỗi phép toán tăng một phần tử lên 1. Thực hiện tối đa k phép. Tìm giá trị xuất hiện nhiều nhất có thể đạt được. Nếu có nhiều giải pháp, chọn số nhỏ nhất.

Ví dụ: nums = [1, 0, 0, 0, 8, 8, 8, 8], k = 8 → đầu ra 8 (tăng 1 lên 8 tốn 7, tăng một 0 lên 1 tốn 1, còn lại 0, được 5 số 8).

Giải thuật (Cửa sổ trượt trên mảng đã sắp xếp)

1. Sắp xếp nums.
2. Khởi tạo low = 0, high = 0, dist = 0, best = 0, ret = -1.
3. Khi high < len(nums):
   • Nếu high > 0 và nums[high] != nums[high-1]: dist += (high - low) * (nums[high] - nums[high-1]).
   • high += 1.
   • Khi dist > k: dist -= nums[high-1] - nums[low], low += 1.
   • Nếu high - low > best: best = high - low, ret = nums[high-1].
4. Trả về ret.

Ví dụ mã Python

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

Đầu vào

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

Đầu ra

8