Как узнать, является ли список подмножеством другого списка?
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
- 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;
}
Другие решения
Вы предполагаете, что элемент q, которого нет в p, всегда находится в самом конце списка. Вы должны принять во внимание, что дополнительный элемент может находиться в любом месте списка, а не только в конце списка, и вы будете на правильном пути.