คำอธิบายปัญหา
กำหนดลิสต์ nums เรียงจากน้อยไปมาก และค่า target หาดัชนีที่ควรแทรก target เพื่อให้ลิสต์ยังคงเรียงลำดับ หาก target มีอยู่แล้ว ให้คืนดัชนีที่มากที่สุดที่สามารถแทรกได้ (ด้านขวาสุด) ต้องแก้ใน O(log n) โดยไม่ใช้ฟังก์ชันไลบรารี
ตัวอย่าง
nums = [1, 5, 6, 6, 8, 9], target = 6 → Output: 4 (แทรกหลัง 6 ตัวสุดท้าย → [1, 5, 6, 6, 6, 8, 9])
ขั้นตอนการแก้ปัญหา (Binary Search)
- ตั้ง
left = 0, right = len(nums) - 1, ans = 0 - วนลูป
while left <= right:mid = (left + right) // 2- ถ้า
target >= nums[mid]:ans = mid + 1, left = mid + 1(ค้นหาต่อทางขวา) - มิฉะนั้น:
right = mid - 1
- คืนค่า
ans
การตนการทำงาน (Python)
def solve(nums, target):
left, right = 0, len(nums) - 1
ans = 0
while left <= right:
mid = (left + right) // 2
if target >= nums[mid]:
ans = mid + 1
left = mid + 1
else:
right = mid - 1
return ans
nums = [1, 5, 6, 6, 8, 9]
target = 6
print(solve(nums, target)) # Output: 4
อินพุต / เอาต์พุต
Input: [1, 5, 6, 6, 8, 9], 6 Output: 4
