สมมติว่าเรามีรายการจำนวนบวกที่ไม่ซ้ำที่เรียงกันเป็นทวีคูณ เราต้องหาคู่ในรายการที่เชื่อมโยงเป็นสองเท่าซึ่งผลิตภัณฑ์นั้นเหมือนกับค่าที่กำหนด x เราต้องจำไว้ว่าสิ่งนี้จะได้รับการแก้ไขโดยไม่ต้องใช้พื้นที่เพิ่มเติม
ดังนั้น หากอินพุตเป็นเหมือน L =1 ⇔ 2 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 8 ⇔ 9 และ x =8 ผลลัพธ์จะเป็น (1, 8), (2, 4)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
curr :=หัว nxt :=หัว
-
ในขณะที่ nxt.next ไม่ใช่ None ไม่ใช่ศูนย์ ให้ทำ
-
nxt :=nxt.next
-
-
พบ :=เท็จ
-
ในขณะที่ curr และ nxt ไม่เป็นโมฆะ และ curr และ nxt ต่างกันและ nxt.next ไม่ใช่ curr ให้ทำ
-
ถ้า (curr.data * nxt.data) เหมือนกับ x แล้ว
-
พบ :=จริง
-
แสดงคู่ curr.data, nxt.data
-
curr :=curr.next
-
nxt :=nxt.prev
-
-
มิฉะนั้น
-
if (curr.data * nxt.data)
-
curr :=curr.next
-
-
มิฉะนั้น
-
nxt :=nxt.prev
-
-
-
-
หากพบว่าเป็นเท็จ
-
แสดง "ไม่พบ"
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class ListNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert(head, data):
node = ListNode(0)
node.data = data
node.next = node.prev = None
if (head == None):
(head) = node
else :
node.next = head
head.prev = node
head = node
return head
def get_pair_prod(head, x):
curr = head
nxt = head
while (nxt.next != None):
nxt = nxt.next
found = False
while (curr != None and nxt != None and curr != nxt and nxt.next != curr) :
if ((curr.data * nxt.data) == x) :
found = True
print("(", curr.data, ", ", nxt.data, ")")
curr = curr.next
nxt = nxt.prev
else :
if ((curr.data * nxt.data) < x):
curr = curr.next
else:
nxt = nxt.prev
if (found == False):
print( "Not found")
head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
get_pair_prod(head, x) อินพุต
head = None head = insert(head, 9) head = insert(head, 8) head = insert(head, 6) head = insert(head, 5) head = insert(head, 4) head = insert(head, 2) head = insert(head, 1) x = 8
ผลลัพธ์
( 1 , 8 ) ( 2 , 4 )
