数据结构
网络
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 浏览量
广告