컨셉
긍정적인 고유 요소의 주어진 정렬된 이중 연결 목록과 관련하여 우리의 작업은 추가 공간을 소비하지 않고 주어진 값 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를 의미합니다.
이제 첫 번째 및 두 번째 포인터를 첫 번째 및 마지막 노드로 초기화합니다. 이 경우에는 임의의 액세스 권한이 없으므로 두 번째 포인터를 결정하기 위해 목록을 방문하여 second1을 초기화합니다.
first1과 second1의 현재 합이 x보다 작으면 first1을 순방향으로 이동하는 것으로 나타났습니다. 그렇지 않고 first1과 second1의 현재 합이 x보다 크면 우리는 second1을 역방향으로 이동합니다.
마지막으로 루프 종료 조건도 어레이와 다릅니다. 이 경우 루프는 두 포인터 중 하나가 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)