Giả sử chúng ta có một dãy nums và một giá trị k khác. Trong một thao tác, chúng ta có thể chọn một số chỉ mục và tăng phần tử tại chỉ mục đó lên 1. Chúng ta phải tìm tần suất tối đa có thể có của một phần tử sau khi thực hiện nhiều nhất k số thao tác.
Vì vậy, nếu đầu vào giống như nums =[8,3,6], k =9, thì đầu ra sẽ là 3 vì chúng ta có thể cập nhật 3 bằng 5, 6 bằng 2, để làm cho nó [8,8,8] như vậy sau 7 hoạt động, chúng tôi có tần suất tối đa 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp số lượng danh sách
-
left:=0, right:=1
-
trong khi bên phải
-
k:=k - (nums [right] - nums [right-1]) * (right - left)
-
nếu k <0, thì
-
k:=k + nums [right] - nums [left]
-
left:=left + 1
-
-
right:=right + 1
-
-
quay lại phải - trái
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(nums, k):
nums.sort()
left = 0
right = 1
while right < len(nums):
k -= (nums[right] - nums[right-1]) * (right - left)
if k < 0:
k += nums[right] - nums[left]
left += 1
right += 1
return right - left
nums = [8,3,6]
k = 9
print(solve(nums, k))
Đầu vào
[8,3,6], 9
Đầu ra
3