ปัญหา
ให้อาร์เรย์ nums ตรวจสอบว่าประกอบด้วยจำนวนเต็มติดกันหรือไม่
ตัวอย่าง
nums = [6, 8, 3, 5, 4, 7] → เรียงได้ 3,4,5,6,7,8 → True
แนวคิดการแก้ปัญหา (O(n) time, O(1) space แบบแก้ไขอาร์เรย์)
- หา min, max
- ถ้า max - min + 1 != n → False
- ใช้วิธี "ทำเครื่องหมาย" โดยทำให้ค่าที่ index ตรงกันเป็นลบ
- ถ้าพบค่าลบซ้ำ → มี duplicate → False
โค้ดตัวอย่าง
def solve(nums):
n = len(nums)
if n == 0:
return False
min_val, max_val = min(nums), max(nums)
if max_val - min_val + 1 != n:
return False
for i in range(n):
# หา index ที่ควรจะอยู่
val = abs(nums[i])
j = val - min_val
if nums[j] > 0:
nums[j] = -nums[j]
else:
return False # duplicate
return True
print(solve([6, 8, 3, 5, 4, 7])) # True
หมายเหตุ
วิธีนี้แก้ไขอาร์เรย์ต้นฉบับ (in-place) ถ้าต้องการเก็บค่าเดิม ให้ copy ก่อน
อินพุต / เอาต์พุต
Input: [6, 8, 3, 5, 4, 7] Output: True
