Chúng tôi có một tập hợp các phần tử. Và một sản phẩm K. Nhiệm vụ là kiểm tra xem trong danh sách liên kết có tồn tại hai số không, có tích nào giống sản phẩm K. Nếu có hai số thì in ra, nếu có nhiều hơn hai số thì in ra. . Giả sử danh sách được liên kết như thế này {2, 4, 8, 12, 15} và k giá trị là 16. thì nó sẽ trả về (2, 8)
Chúng tôi sẽ giải quyết vấn đề này bằng cách sử dụng kỹ thuật băm. Lấy một bảng băm và đánh dấu tất cả các phần tử là 0. Bây giờ, đánh dấu lặp lại tất cả các phần tử là 1 trong bảng băm, nếu điều đó có trong danh sách được liên kết. Bây giờ hãy bắt đầu xem qua danh sách được liên kết và kiểm tra xem sản phẩm đã cho có chia hết cho phần tử hiện tại hay không. Nếu có, hãy kiểm tra xem (K / phần tử hiện tại) của danh sách liên kết có trong bảng băm hay không.
Ví dụ
#include <unordered_set>
#define MAX 100000
using namespace std;
class Node {
public:
int data;
Node* next;
};
void append(struct Node** start, int key) {
Node* new_node = new Node;
new_node->data = key;
new_node->next = (*start);
(*start) = new_node;
}
bool isPairPresent(Node* start, int K) {
unordered_set<int> s;
Node* p = start;
while (p != NULL) {
int current = p->data;
if ((K % current == 0) && (s.find(K / current) != s.end())) {
cout << current << " " << K / current;
return true;
}
s.insert(p->data);
p = p->next;
}
return false;
}
int main() {
Node* start = NULL;
int arr[] = {2, 4, 8, 12, 15};
int n = sizeof(arr)/sizeof(arr[0]);
for(int i = 0; i<n; i++){
append(&start, arr[i]);
}
if (isPairPresent(start, 16) == false)
cout << "NO PAIR EXIST";
} Đầu ra
2 8