요소 집합이 있습니다. 그리고 제품 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