Tìm cặp có tích cho trước trong danh sách liên kết đôi đã sắp xếp trong C++

Khái niệm

Cho danh sách liên kết đôi (DLL) đã sắp xếp chứa các phần tử dương phân biệt. Tìm các cặp trong DLL có tích bằng giá trị x cho trước, không dùng bộ nhớ thêm.

Ví dụ 1

Đầu vào: List = 1 ⇔ 2 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 8 ⇔ 9, x = 8

Đầu ra: (1, 8), (2, 4)

Ví dụ 2

Đầu vào: List = 1 ⇔ 2 ⇔ 3 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 7, x = 6

Đầu ra: (1, 6), (2, 3)

Phương pháp

Cách đơn giản: Duyệt hai vòng lặp lồng, kiểm tra tất cả cặp, độ phức tạp O(n^2).

Cách hiệu quả: Dùng hai con trỏ: first trỏ đầu, second trỏ cuối. Vì DLL đã sắp xếp, nếu tích first*second < x thì tiến first lên, nếu > x thì lùi second xuống. Dừng khi con trỏ gặp nhau hoặc NULL.

Ví dụ

// Chương trình C++ tìm cặp có tích x trong DLL đã sắp xếp
#include <bits/stdc++.h>
using namespace std;

struct Node1 {
    int data1;
    struct Node1 *next1, *prev1;
};

void pairProduct(struct Node1* head1, int x1) {
    struct Node1* first1 = head1;
    struct Node1* second1 = head1;
    while (second1->next1 != NULL)
        second1 = second1->next1;
    bool found1 = false;
    while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
        if ((first1->data1 * second1->data1) == x1) {
            found1 = true;
            cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
            first1 = first1->next1;
            second1 = second1->prev1;
        } else {
            if ((first1->data1 * second1->data1) < x1)
                first1 = first1->next1;
            else
                second1 = second1->prev1;
        }
    }
    if (!found1)
        cout << "Không tìm thấy cặp";
}

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;
    }
}

int main() {
    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;
}

Đầu ra

(1, 6) (2, 3)