struct Node {
int value;
Node* next;
};
bool propSubset(Node* p, Node* q) {
if(q == nullptr) return false;
if(p == nullptr && q != nullptr) return true;
if(p->value < q->value) return false;
if(p->value > q->value) return propSubset(p, q->next);
return propSubset(p->next, q->next);
}
p 是 q 的子集如果
- p的所有元素都是q的元素
- q至少有一个元素不在p中。
p和q都是升序排列
这就是我得到的全部,但它不适用于 p = {2, 4}, q = {1, 2, 3, 4}
我该如何改进呢?谢谢
最佳答案
迭代解决方案可能会更好。给定任意长度的列表,您不希望冒用完堆栈空间的风险。
由于 q 中的非交叉元素可以随机分布,因此大小因素也发挥了作用。
您可能想要重构您的代码,例如:
bool propSubset(Node* p, Node* q) {
int len_q = length(q); // assuming you have length function.
if (length(p) >= len_q) return false;
for(int i=0; i < len_q && p != nullptr; ++i) {
if (p->value == q->value) p = p->next;
if (p->value < q->value) return false; // That particular value in p is not in q.
q = q->next;
}
if (p == nullptr) return true;
return false;
}
关于c++ - 如何查找列表是否是另一个列表的子集?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23005238/