สมมติว่าเรามีอาร์เรย์ nums เราสามารถเปลี่ยนค่าอะไรก็ได้ของอิลิเมนต์หนึ่งในหนึ่งครั้ง (move) เราต้องหาความต่างน้อยที่สุดระหว่างค่าสูงสุดและต่ำสุดของ nums หลังจากทำได้สูงสุด 3 ครั้ง
เช่น ถ้าข้อมูลเข้าเป็น nums = [3,7,2,12,16] ผลลัพธ์จะเป็น 1 เพราะเราสามารถทำให้อาร์เรย์กลายเป็น [1,1,0,1,1] ค่าสูงสุดคือ 1 ค่าต่ำสุดคือ 0 ความต่างคือ 1
ขั้นตอนการแก้ปัญหา
- ถ้าขนาด nums ≤ 4 ให้คืน 0 (เพราะสามารถทำให้ทุกค่าเท่ากันได้)
- เรียงลำดับ nums จากน้อยไปมาก
- กำหนด ans = infinity
- วนลูป i จาก 0 ถึง 3:
- mi = nums[i] (ค่าต่ำสุดที่อาจเหลือหลังลบ i ตัวแรก)
- ma = nums[-(3-i+1)] (ค่าสูงสุดที่อาจเหลือหลังลบ 3-i ตัวท้าย)
- ans = min(ans, ma - mi)
- คืนค่า ans
ตัวอย่างโค้ด
def solve(nums):
if len(nums) <= 4:
return 0
nums.sort()
ans = float("inf")
for i in range(4):
mi = nums[i]
ma = nums[-(3 - i + 1)]
ans = min(ma - mi, ans)
return ans
nums = [3,7,2,12,16]
print(solve(nums))
ข้อมูลเข้า
[3,7,2,12,16]
ข้อมูลออก
1
