เรามีชุดขององค์ประกอบ และผลิตภัณฑ์ K งานคือตรวจสอบว่ามีตัวเลขสองตัวในรายการที่เชื่อมโยงซึ่งมีสินค้าเหมือนกับ K หรือไม่ ถ้ามีสองตัวให้พิมพ์ออกมาถ้ามีมากกว่าสองตัวให้พิมพ์ตัวใดตัวหนึ่ง . สมมติว่ารายการที่เชื่อมโยงเป็นเช่นนี้ {2, 4, 8, 12, 15} และค่า k คือ 16 จากนั้นจะส่งคืน (2, 8)
เราจะแก้ปัญหานี้โดยใช้เทคนิคการแฮช ใช้ตารางแฮชหนึ่งตาราง และทำเครื่องหมายองค์ประกอบทั้งหมดเป็น 0 ตอนนี้ ให้ทำเครื่องหมายองค์ประกอบทั้งหมดซ้ำเป็น 1 ในตารางแฮช หากมีอยู่ในรายการที่เชื่อมโยง ตอนนี้ เริ่มต้นสำรวจรายการที่เชื่อมโยง และตรวจสอบว่าผลิตภัณฑ์ที่กำหนดนั้นหารด้วยองค์ประกอบปัจจุบันหรือไม่ ถ้าใช่ ให้ตรวจสอบว่า (องค์ประกอบ K/ปัจจุบัน) ของรายการที่เชื่อมโยงมีอยู่ในตารางแฮชหรือไม่
ตัวอย่าง
#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";
} ผลลัพธ์
2 8
