資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中檢查連結串列中是否存在乘積等於給定值得兩數
我們有一組元素。以及一個乘積 K。任務是檢查連結串列中是否存在兩個數字，其乘積與 K 相同。如果有兩個數字，則列印它們，如果有多於兩個數字，則列印任意一對。假設連結串列如下 {2, 4, 8, 12, 15}，k 值為 16。然後它將返回 (2, 8)。
我們將使用雜湊技術解決此問題。取一個雜湊表，並將所有元素標記為 0。現在，如果雜湊表中存在該元素，則將所有元素迭代標記為 1。現在開始遍歷連結串列，並檢查給定的乘積是否除以當前元素。如果是，則檢查連結串列的 (K/current element) 是否存在於雜湊表中。
示例
#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
更新於: 2019-10-22
131 瀏覽量
廣告