ค้นหาคู่สำหรับผลรวมที่กำหนดในลิงก์ที่เรียงลำดับโดยไม่มีช่องว่างเพิ่มเติมใน C ++

สมมติว่าเรามีรายการที่เชื่อมโยงเพียงอย่างเดียวและมีค่า x; เราต้องหาคู่ที่มีผลรวมเท่ากับ x เราต้องจำไว้ว่าเราไม่สามารถใช้ช่องว่างเพิ่มเติมได้และความซับซ้อนของเวลาที่คาดหวังจะเป็น O(n)

ดังนั้น หากอินพุตเป็น 4→7→8→9→10→11→12, x =19 ผลลัพธ์จะเป็น [(7, 12), (8, 11), (9, 10)]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน convert_to_xor() สิ่งนี้จะเริ่มต้น

• ก่อนหน้า :=NULL

• ในขณะที่การเริ่มต้นเป็น NULL ให้ทำ -

  • next_list_node :=ถัดไปของการเริ่มต้น

  • next of start :=XOR ของ address ของ next_list_node และ prev

  • ก่อนหน้า :=เริ่ม

  • start :=next_list_node

• จากวิธีหลัก ให้ทำดังนี้ −

• ก่อน :=เริ่ม

• next_list_node :=NULL, ก่อนหน้า :=NULL, วินาที :=start

• ในขณะที่วินาทีถัดไปไม่เท่ากับก่อนหน้า ให้ทำ -

  • อุณหภูมิ :=วินาที

  • วินาที :=XOR ของที่อยู่ (ถัดไปของวินาที ก่อนหน้า)

  • ก่อนหน้า :=อุณหภูมิ

• next_list_node :=NULL

• ก่อนหน้า :=NULL

• ธง :=เท็จ

• ในขณะที่ (อันแรกไม่เท่ากับ NULL และอันที่สองไม่เท่ากับ NULL และอันแรกไม่เท่ากับวินาที และอันแรกไม่เท่ากับ next_list_node) ทำ -

  • ถ้าข้อมูลของตัวแรก + ข้อมูลของวินาทีเหมือนกับ x แล้ว −

    • แสดงข้อมูลคู่ของครั้งแรก ข้อมูลของวินาที

    • ธง :=จริง

    • temp :=ก่อน

    • first :=XOR ของที่อยู่ของ (ถัดจาก first,prev)

    • ก่อนหน้า :=อุณหภูมิ

    • อุณหภูมิ :=วินาที

    • วินาที :=XOR ของที่อยู่ของวินาทีถัดไป next_list_node)

    • next_list_node :=อุณหภูมิ

  • มิฉะนั้น

    • ถ้า data ของ first + data ของวินาที

      • temp :=ก่อน

      • first :=XOR ของที่อยู่ของ (ถัดจาก first,prev)

      • ก่อนหน้า :=อุณหภูมิ

    • มิฉะนั้น

      • อุณหภูมิ :=วินาที

      • วินาที :=XOR ของที่อยู่ของ (วินาทีถัดไป, next_list_node)

      • next_list_node :=อุณหภูมิ

• ถ้าแฟล็กเหมือนกับเท็จ ดังนั้น −

  • ไม่มีคู่

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include<bits/stdc++.h>
using namespace std;
class ListNode {
public:
   int data;
   ListNode *next;
   ListNode(int data) {
      this->data = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v) {
   ListNode *start = new ListNode(v[0]);
   for (int i = 1; i < v.size(); i++) {
      ListNode *ptr = start;
      while (ptr->next != NULL) {
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return start;
}
ListNode* XOR (ListNode *a, ListNode *b) {
   return (ListNode*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
void convert_to_xor(ListNode *start) {
   ListNode *next_list_node;
   ListNode *prev = NULL;
   while (start != NULL) {
      next_list_node = start->next;
      start->next = XOR(next_list_node, prev);
      prev = start;
      start = next_list_node;
   }
}
void get_pared_sum(ListNode *start, int x) {
   ListNode *first = start;
   ListNode *next_list_node = NULL, *prev = NULL;
   ListNode *second = start;
   while (second->next != prev) {
      ListNode *temp = second;
      second = XOR(second->next, prev);
      prev = temp;
   }
   next_list_node = NULL;
   prev = NULL;
   bool flag = false;
   while (first != NULL && second != NULL && first != second && first != next_list_node) {
      if ((first->data + second->data)==x) {
         cout << "(" << first->data << ","<< second->data << ")" << endl;
         flag = true;
         ListNode *temp = first;
         first = XOR(first->next,prev);
         prev = temp;
         temp = second;
         second = XOR(second->next, next_list_node);
         next_list_node = temp;
      }
      else{
         if ((first->data + second->data) < x) {
            ListNode *temp = first;
            first = XOR(first->next,prev);
            prev = temp;
         }
         else{
            ListNode *temp = second;
            second = XOR(second->next, next_list_node);
            next_list_node = temp;
         }
      }
   }
   if (flag == false)
      cout << "No pair found" << endl;
}
int main() {
   vector<int> v = {4,7,8,9,10,11,12};
   ListNode* start = make_list(v);
   int x = 19;
   convert_to_xor(start);
   get_pared_sum(start,x);
}

อินพุต

{4,7,8,9,10,11,12}

ผลลัพธ์

(7,12) (8,11) (9,10)