หาคู่ที่มีผลคูณกำหนดใน Doubly Linked List ที่เรียงลำดับแล้วใน C++

แนวคิด

สำหรับ Doubly Linked List ที่เรียงลำดับแล้วของสมาชิกบวกที่ไม่ซ้ำกัน ภารกิจของเราคือหาคู่ใน Doubly Linked List ที่ผลคูณเท่ากับค่า x ที่กำหนด โดยไม่ใช้พื้นที่เพิ่มเติม (extra space)

อินพุต

List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9, x = 8

เอาต์พุต

(1, 8), (2, 4)

อินพุต

List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7, x = 6

เอาต์พุต

(1, 4), (2, 3)

วิธีการ

ตาม Simple Approach เราเดิน linked list ด้วย nested loops สองชั้นหาคู่ทั้งหมดและตรวจสอบคู่ที่ผลคูณเท่ากับ x Time complexity จะเป็น O(n^2) โดย n คือจำนวนโหนดทั้งหมด

Efficient Solution ที่มีประสิทธิภาพกว่านี้ ขั้นตอนของอัลกอริทึม:

• กำหนด pointer สองตัวเพื่อหาสมาชิกที่เป็นผู้สมัครใน sorted doubly linked list
• กำหนด first1 ให้ชี้ที่ head (เริ่มต้น) และ second1 ให้ชี้ที่ last_node (ท้าย)
• เริ่มต้น first และ second pointers เป็น first และ last nodes เนื่องจากไม่มี random access การหา second pointer ต้องเดิน list จนถึงท้าย
• ถ้าผลคูณของ first1 และ second1 น้อยกว่า x ให้เลื่อน first1 ไปข้างหน้า ถ้ามากกว่า x ให้เลื่อน second1 ไปข้างหลัง
• เงื่อนไขหยุดลูปต่างจาก array: ลูปจบเมื่อ pointer ใด pointer หนึ่งเป็น NULL หรือพวกมันทับซ้อนกัน (second1->next == first1) หรือกลายเป็นตัวเดียวกัน (first1 == second1)

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

// C++ program to find a pair with
// given product x in sorted Doubly
// Linked List
#include <bits/stdc++.h>
using namespace std;

// Doubly Linked List Node
struct Node1 {
    int data1;
    struct Node1 *next1, *prev1;
};

// ฟังก์ชันหาคู่ที่ผลคูณเท่ากับ x
void pairProduct(struct Node1* head1, int x1) {
    // กำหนด two pointers
    // first at beginning of DLL, second at end of DLL
    struct Node1* first1 = head1;
    struct Node1* second1 = head1;
    while (second1->next1 != NULL)
        second1 = second1->next1;
    
    // ติดตามว่าพบคู่หรือไม่
    bool found1 = false;
    
    // ลูปจบเมื่อ pointer ใดเป็น NULL หรือทับซ้อนหรือเหมือนกัน
    while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
        // พบคู่
        if ((first1->data1 * second1->data1) == x1) {
            found1 = true;
            cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
            // เลื่อน first ไปข้างหน้า
            first1 = first1->next1;
            // เลื่อน second ไปข้างหลัง
            second1 = second1->prev1;
        } else {
            if ((first1->data1 * second1->data1) < x1)
                first1 = first1->next1;
            else
                second1 = second1->prev1;
        }
    }
    
    // ถ้าไม่พบคู่
    if (found1 == false)
        cout << "No pair found";
}

// ฟังก์ชันช่วยสร้างโหนดใหม่ที่ head
void insert(struct Node1** head1, int data1) {
    struct Node1* temp1 = new Node1;
    temp1->data1 = data1;
    temp1->next1 = temp1->prev1 = NULL;
    if (!(*head1))
        (*head1) = temp1;
    else {
        temp1->next1 = *head1;
        (*head1)->prev1 = temp1;
        (*head1) = temp1;
    }
}

// Driver Code
int main() {
    // สร้าง Doubly Linked List
    struct Node1* head1 = NULL;
    insert(&head1, 7);
    insert(&head1, 6);
    insert(&head1, 5);
    insert(&head1, 4);
    insert(&head1, 3);
    insert(&head1, 2);
    insert(&head1, 1);
    int x1 = 6;
    pairProduct(head1, x1);
    return 0;
}

ผลลัพธ์

(1, 6) (2, 3)