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

ปัญหา

อาร์เรย์ nums และ k Operations: เลือก Index ใดๆ เพิ่มค่า 1 หา Max Frequency ของ Element ใด Element หลัง ≤ k Operations

ตัวอย่าง

nums = [8,3,6], k = 9 → Output: 3

เพิ่ม 3→8 (5 ops), 6→8 (2 ops) → [8,8,8] ใช้ 7 ops ≤ 9, Freq = 3

อัลกอริทึม (Sliding Window + Sort)

1. Sort Array
2. Sliding Window [left, right] รักษา Invariant: Cost ทำให้ทุกค่าใน Window = nums[right] ≤ k
3. Cost = Σ(nums[right] - nums[i]) = (right-left)×nums[right] - Sum(window[:-1])
4. Incremental Update: เพิ่ม right → Cost += (nums[right]-nums[right-1])×(right-left)
5. ถ้า Cost > k: left++ และ Cost -= nums[right] - nums[left]

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

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

ความซับซ้อน

• Time: O(n log n) จาก Sort
• Space: O(1)

Sliding Window บน Sorted Array ใช้ความจริงว่า Optimal Target = Max ใน Window