สมมุติว่าเรามีอาร์เรย์จำนวน n จำนวนที่แตกต่างกัน n สามารถเป็น 32,000 ที่สูงสุด อาร์เรย์อาจมีรายการที่ซ้ำกันและเราไม่ทราบว่าค่าของ n คืออะไร ตอนนี้ถ้าเรามีหน่วยความจำเพียง 4 กิโลไบต์ จะแสดงข้อมูลที่ซ้ำกันทั้งหมดในอาร์เรย์อย่างไร
ดังนั้น หากอินพุตเป็น [2, 6, 2, 11, 13, 11] เอาต์พุตจะเป็น [2,11] เนื่องจาก 2 และ 11 ปรากฏขึ้นมากกว่าหนึ่งครั้งในอาร์เรย์ที่กำหนด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
สร้างโครงสร้างข้อมูลแบบไบต์อาเรย์หนึ่งชนิด bit_arr โดยมีวิธีการดังต่อไปนี้
-
กำหนดคอนสตรัคเตอร์ สิ่งนี้จะใช้เวลา n
-
arr :=อาร์เรย์ขนาด (n / 2^5) + 1 เติมด้วย 0
-
กำหนดฟังก์ชัน get_val() นี่จะใช้เวลา pos
-
ดัชนี :=pos / 2^5
-
bitNo :=pos และ 31
-
คืนค่าจริงเมื่อ (arr[index] AND (2^bitNo)) ไม่เหมือนกับ 0
-
กำหนดฟังก์ชัน set_val() นี่จะใช้เวลา pos
-
ดัชนี :=pos / 2^5
-
bitNo :=pos และ 31
-
arr[index] :=arr[index] OR (2^bitNo)
-
จากวิธีหลัก ให้ทำดังนี้ −
-
arr :=bit_arr(320000)
-
สำหรับฉันในช่วง 0 ถึงขนาดของ arr ทำ
-
num :=arr[i]
-
ถ้า arr.get_val(num) ไม่ใช่ศูนย์ ดังนั้น
-
แสดงจำนวน
-
-
มิฉะนั้น
-
set_val(num) ของ arr
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class bit_arr: def __init__(self, n): self.arr = [0] * ((n >> 5) + 1) def get_val(self, pos): self.index = pos >> 5 self.bitNo = pos & 31 return (self.arr[self.index] & (1 << self.bitNo)) != 0 def set_val(self, pos): self.index = pos >> 5 self.bitNo = pos & 31 self.arr[self.index] |= (1 << self.bitNo) def is_duplicate(arr): arr = bit_arr(320000) for i in range(len(arr)): num = arr[i] if arr.get_val(num): print(num, end = " ") else: arr.set_val(num) arr = [2, 6, 2, 11, 13, 11] is_duplicate(arr)
อินพุต
[2, 6, 2, 11, 13, 11]
ผลลัพธ์
2 11
