Ежедневная часть (e) C++ # 16, Общий вопрос интервью: Объединение отсортированных списков с поворотом C++
Сегодня мы рассмотрим еще один распространенный вопрос на собеседовании — объединение отсортированных списков.
Однако, поскольку это C++, мы сделаем небольшую поправку и добавим требование избегать ненужных копий.
Постановка проблемы
Учитывая отсортированные списки как std::vector<std::forward_list<>>, создайте объединенные отсортированные std::forward_list<>.
Ваша реализация должна заботиться о сложности big-O и избегать ненужных копий.
Для этого ввод задается по значению и может быть изменен.
Прежде чем читать решение, попробуйте решить его самостоятельно: https://compiler-explorer.com/z/5raraWG5f.
Решение
У нас есть два варианта решения этой проблемы.
Мы можем либо повторно выбрать список с наименьшим ведущим элементом, что приведет к n (количество элементов) повторений log(k) (выбор наименьшего элемента).
Или мы можем многократно объединять пары списков, что приводит к log(k) (поскольку мы делим количество списков на два в каждой итерации) повторений n операций во время слияния.
Есть несколько мест, где нам нужно быть осторожными с копиями. Во-первых, при перемещении списков нам нужно поменять местами или переместить их.
Во-вторых, для первого решения нам понадобится упорядоченная структура данных. Всякий раз, когда мы извлекаем первый элемент из списка, нам нужно извлечь список из структуры данных и только потом модифицировать его. Это потенциальное место, где могут быть представлены копии, поэтому нам нужно быть осторожными.
Решение A (повторно выберите список с наименьшим ведущим элементом):
std::forward_list<int> merge(std::vector<std::forward_list<int>> in) {
using fwlst = std::forward_list<int>;
// Custom comparator, compare based on the first element
auto cmp = [](const fwlst& l, const fwlst& r) {
return l.front() < r.front();
};
// View of non-empty lists, if we filter here,
// we don't have to check later.
auto non_empty = in |
std::views::filter(std::not_fn(&fwlst::empty)) |
std::views::common;
// Consume the input using std::move_iterator,
// avoids making copies of the lists.
std::multiset<fwlst,decltype(cmp)> q(
std::move_iterator(non_empty.begin()),
std::move_iterator(non_empty.end()),
cmp);
fwlst result;
fwlst::iterator tail = result.before_begin();
while (!q.empty()) {
// Extract the node that holds the element,
// without making a copy
auto top = q.extract(q.begin());
// Splice the first element of the top list to the result
result.splice_after(tail,
top.value(), top.value().before_begin());
++tail;
if (!top.value().empty())
q.insert(std::move(top)); // put back
}
// Each element is the minimum once, therefore the main loop
// will loop O(n) times, where n is the total number of elements.
// The insert is our only non-constant operation, meaning that
// we end up with O(n*logk), where k is the number of lists.
return result;
}
Нажмите здесь, чтобы открыть решение в Compiler Explorer.
Решение B (многократное объединение пар списков):
std::forward_list<int> merge_binary(
std::vector<std::forward_list<int>> in) {
auto tail = in.begin();
auto end = in.end();
// While we have more than one list
while (std::distance(in.begin(), end) > 1) {
auto it = in.begin();
// Take a pair of lists
while (it != end && std::next(it) != end) {
// Merge
it->merge(*std::next(it));
// and shift to the begining of the array
tail->swap(*it);
++tail;
std::advance(it, 2);
}
// If we have odd number of lists
if (it != end) {
tail->swap(*it);
++tail;
}
// The new end is one behind the last moved list
end = tail;
tail = in.begin();
}
// The content of the main loop is O(n), as each merge is O(m),
// where m the total number of elements in both lists.
// We will repeat the main loop O(logk) times, since
// we divide the number of lists by two each iteration.
// Hence, again O(n*logk).
return in[0];
}
