Chương trình tìm giá trị lớn nhất nhỏ nhất có thể sau k phép toán trong Python

Mô tả bài toán

Cho một danh sách số nums và một giá trị k. Mỗi phép toán cho phép trừ 1 từ một phần tử bất kỳ trong danh sách. Thực hiện đúng k phép toán. Tìm giá trị lớn nhất nhỏ nhất có thể của danh sách sau các phép toán.

Ví dụ: nums = [3, 4, 6, 5], k = 6 → đầu ra 3, vì có thể giảm 4 một lần, 6 ba lần và 5 hai lần để được [3, 3, 3, 3].

Giải thuật

1. Sắp xếp danh sách theo thứ tự giảm dần.
2. Khởi tạo i = 0, curr = nums[0].
3. Trong khi k > 0:
   • Tăng i cho đến khi nums[i] != curr (đếm số phần tử bằng giá trị lớn nhất hiện tại).
   • Nếu k >= i: trừ i từ k, giảm curr đi 1.
   • Ngược lại: trả về curr.
4. Trả về curr.

Ví dụ mã Python

class Solution:
    def solve(self, nums, k):
        nums.sort(reverse=True)
        i = 0
        curr = nums[0]
        while k > 0:
            while i < len(nums) and nums[i] == curr:
                i += 1
            if k >= i:
                k -= i
                curr -= 1
            else:
                return curr
        return curr

ob = Solution()
nums = [3, 4, 6, 5]
k = 6
print(ob.solve(nums, k))

Đầu vào

[3, 4, 6, 5], 6

Đầu ra

3