โปรแกรมหา Amplitude น้อยที่สุดหลังลบ K องค์ประกอบใน Python

การหา Amplitude (max - min) น้อยที่สุดหลังลบ k องค์ประกอบ

กำหนดรายการ nums และ k ลบ k องค์ประกอบใด ๆ ออก หา amplitude = max(เหลือ) - min(เหลือ) น้อยที่สุด

อัลกอริทึม

1. เรียง nums จากน้อยไปมาก
2. p = n - k (จำนวนองค์ประกอบที่เหลือ)
3. พิจารณาหน้าต่างขนาด p ในอาร์เรย์ที่เรียงแล้ว
4. amplitude ของหน้าต่าง = nums[i+p-1] - nums[i]
5. หาค่าน้อยสุดของ amplitude ทุกหน้าต่าง

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

def solve(nums, k):
    nums = sorted(nums)
    p = len(nums) - k
    m = nums[-1] - nums[0]
    for i in range(0, len(nums) - p + 1):
        if nums[i + p - 1] - nums[i] < m:
            m = nums[i + p - 1] - nums[i]
    return m

nums = [10, 4, 3, 2, 9, 8]
k = 3
print(solve(nums, k))

ผลลัพธ์

2

คำอธิบาย

เรียง: [2, 3, 4, 8, 9, 10], k=3 → p=3

หน้าต่างขนาด 3: [2,3,4]→2, [3,4,8]→5, [4,8,9]→5, [8,9,10]→2 → น้อยสุด = 2

ลบ 10, 8, 9 เหลือ [2,3,4] max=4 min=2 diff=2