ค้นหาคู่กับสินค้าที่ระบุในรายการเชื่อมโยงแบบทวีคูณที่จัดเรียงใน C++

แนวคิด

ในส่วนที่เกี่ยวกับรายการที่เชื่อมโยงแบบทวีคูณซึ่งได้รับการเชื่อมโยงเป็นทวีคูณขององค์ประกอบที่แตกต่างกันในเชิงบวก ภารกิจของเราจะกำหนดคู่ในรายการที่เชื่อมโยงแบบทวีคูณซึ่งมีผลิตภัณฑ์เท่ากับค่าที่กำหนด x โดยไม่ต้องใช้พื้นที่เพิ่มเติม

อินพุต

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)

วิธีการ

ตามแนวทางง่ายๆ สำหรับปัญหานี้ เราสำรวจรายการเชื่อมโยงที่ใช้การวนซ้ำซ้อนสองรายการและกำหนดคู่ทั้งหมดและตรวจสอบคู่ที่มีผลิตภัณฑ์เท่ากับ x ในที่นี้ ความซับซ้อนของเวลาสำหรับปัญหานี้จะเป็น O(n^2) โดยที่ n คือจำนวนโหนดทั้งหมดในรายการที่เชื่อมโยงแบบทวีคูณ

โซลูชั่นที่มีประสิทธิภาพ สำหรับปัญหานี้จะกล่าวถึง นี่คือขั้นตอนของอัลกอริทึม -

เราเริ่มต้นตัวแปรตัวชี้สองตัวเพื่อกำหนดองค์ประกอบตัวเลือกในรายการที่เชื่อมโยงแบบทวีคูณที่จัดเรียงแล้ว

เราเริ่มต้น first1 ด้วยการเริ่มต้นของรายการที่เชื่อมโยงแบบทวีคูณซึ่งหมายถึง first1=head และเริ่มต้น second1 ด้วยโหนดสุดท้ายของรายการที่เชื่อมโยงแบบทวีคูณซึ่งหมายถึง second1=last_node

ตอนนี้เราเริ่มต้นพอยน์เตอร์ตัวแรกและตัวที่สองเป็นโหนดแรกและตัวสุดท้าย ในกรณีนี้ เราไม่มีการเข้าถึงแบบสุ่ม ดังนั้นเพื่อกำหนดตัวชี้ที่สอง เราไปที่รายการเพื่อเริ่มต้นวินาทีที่ 1

จะเห็นได้ว่าหากผลรวมของ first1 และวินาทีที่ 1 ปัจจุบันน้อยกว่า x เราจะเคลื่อน first1 ไปในทิศทางไปข้างหน้า มิฉะนั้น หากผลรวมปัจจุบันของ first1 และ second1 มากกว่า x เราจะเคลื่อนที่วินาทีที่ 1 ไปในทิศทางย้อนกลับ

สุดท้าย เงื่อนไขการสิ้นสุดการวนซ้ำก็แตกต่างจากอาร์เรย์เช่นกัน ในกรณีนี้ การวนซ้ำจะสิ้นสุดลงเมื่อตัวชี้สองตัวใดตัวหนึ่งกลายเป็น 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;
//Shows Doubly Linked List Node
struct Node1 {
   int data1;
   struct Node1 *next1, *prev1;
};
// Shows function to determine pair whose product
// equal to given value x
void pairProduct(struct Node1* head1, int x1){
   // Now set two pointers,
   // first to the beginning of DLL and second to the end of DLL.
   struct Node1* first1 = head1;
   struct Node1* second1 = head1;
   while (second1->next1 != NULL)
      second1 = second1->next1;
   // Used to track if we find a pair or not
   bool found1 = false;
   // Now the loop terminates when either of two pointers
   // become NULL, or they cross each other (second1->next1
   // == first1), or they become same (first1 == second1)
   while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
      // pair found
      if ((first1->data1 * second1->data1) == x1) {
         found1 = true;
         cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
         // Used to move first in forward direction
         first1 = first1->next1;
         // Used to move second in backward direction
         second1 = second1->prev1;
      } else {
         if ((first1->data1 * second1->data1) < x1)
            first1 = first1->next1;
         else
            second1 = second1->prev1;
      }
   }
   // Now if pair is not present
   if (found1 == false)
      cout << "No pair found";
}
// Shows a utility function to insert a new node at the
// beginning of doubly linked list
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(){
   // Create Doubly Linked List struct Node1* head1 = NULL;
   /*insert(&head1, 9);
   insert(&head1, 8);
   insert(&head1, 6);
   insert(&head1, 5);
   insert(&head1, 4);
   insert(&head1, 2);
   insert(&head1, 1);
   int x1 = 8; */
   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)