โจทย์: อาร์เรย์ขนาดสูงสุด 32,000 มีค่าซ้ำ หาค่าซ้ำทั้งหมด โดยใช้หน่วยความจำเพียง 4 KB (bit array)
ตัวอย่าง: [2,6,2,11,13,11] → [2,11]
อัลกอริทึม Bit Array (Bit Vector)
4 KB = 32,768 bits → ครอบคลุมค่า 0 ถึง 32,767 พอดี
- แต่ละ bit แทนว่าค่านั้นเคยเจอหรือยัง
- index = value // 32 (value >> 5)
- bit position = value % 32 (value & 31)
- set bit: arr[index] |= (1 << bitPos)
- test bit: (arr[index] & (1 << bitPos)) != 0
ตัวอย่างโค้ด
class BitArray:
def __init__(self, n):
self.arr = [0] * ((n >> 5) + 1) # n/32 + 1 integers
def get_val(self, pos):
index = pos >> 5
bit_no = pos & 31
return (self.arr[index] & (1 << bit_no)) != 0
def set_val(self, pos):
index = pos >> 5
bit_no = pos & 31
self.arr[index] |= (1 << bit_no)
def find_duplicates(arr):
ba = BitArray(320000) # รองรับค่าสูงสุด 320,000
for num in arr:
if ba.get_val(num):
print(num, end=" ")
else:
ba.set_val(num)
find_duplicates([2, 6, 2, 11, 13, 11]) # 2 11
ผลลัพธ์
2 11
สรุป: Bit Array ใช้พื้นที่ 1/32 ของ boolean array ปกติ เหมาะสำหรับจำกัดหน่วยความจำเด็ดขาด (embedded systems, large datasets) Python list of int ใช้พื้นที่มากกว่า จริงๆ ควรใช้ bytearray หรือ array('I') สำหรับ production
