ตรวจสอบว่าแอรเรย์มีทุก元素ในช่วงที่กำหนดหรือไม่ใน Python

ภาพรวม

บทความนี้แสดงวิธีตรวจสอบว่าแอรเรย์ nums มีทุก元素 ในช่วง [x, y] ครบหรือไม่ โดยใช้เทคนิค "ทำเครื่องหมายด้วยเครื่องหมายลบ" (negation marking) เพื่อใช้พื้นที่ O(1) เพิ่มเติม

อัลกอริทึม

1. คำนวณขนาดช่วง temp_range = y - x
2. วนลูปผ่าน nums: ถ้า |nums[i]| อยู่ในช่วง [x, y] ให้ทำเครื่องหมายที่ดัชนี z = |nums[i]| - x โดยคูณ -1
3. นับจำนวนตำแหน่งที่ถูกทำเครื่องหมาย (ค่าติดลบ) ในช่วง [0, temp_range]
4. ถ้านับครบ temp_range + 1 คืนค่า True มิฉะนั้น False

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

def solve(nums, x, y):
    temp_range = y - x
    for i in range(len(nums)):
        if abs(nums[i]) >= x and abs(nums[i]) <= y:
            z = abs(nums[i]) - x
            if nums[z] > 0:
                nums[z] = -nums[z]
    cnt = 0
    for i in range(temp_range + 1):
        if i >= len(nums):
            break
        if nums[i] > 0:
            return False
        else:
            cnt += 1
    if cnt != temp_range + 1:
        return False
    return True

nums = [5,8,9,6,3,2,4]
x = 2
y = 6
print(solve(nums, x, y))  # True (มี 2,3,4,5,6 ครบ)

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

วิธีนี้แก้ไขแอรเรย์ต้นฉบับ (in-place) โดยใช้เครื่องหมายลบเป็นแฟล็ก ต้องระวังกรณีที่แอรเรย์มีค่าติดลบอยู่แล้ว ควรใช้ค่าสัมบูรณ์ abs() ตอนตรวจสอบ