构建具有一个共同成员的数字对链

Question

我需要构建一对数字链，其中：

在每一对中，第一对小于第二对
为了在两个连续的节点之间形成一条链，它们必须有一个共同的数字。换句话说，当且仅当 a==c、b==c、a==d 或 b==d
一对不能由相同的数字组成。也就是说，如果(a,b)存在，那么a!=b

这可能看起来像一个最长递增子序列，但实际上我想链接具有一个相等成员的连续对。

示例：

Initial list (unordered):
(0,1)
(2,3)
(1,6)
(4,6)
(8,9)
(2,8)
Result:
----- chain #1
(0,1)
(1,6)
(4,6)
----- chain #2
(2,3)
(2,8)
(8,9)

我可以做一个算法来遍历每个单元格的整个列表 (O(n^2))，但我想让它更快，而且我可以灵活地以任何方式对我的初始数组进行排序想要（std::set、std::map、std::unordered_map 等）。我的列表由数万对组成，因此我需要一个在处理时间方面的有效解决方案。

Answer 1

当您管理两个列表时，您可以在 O(N * log(N)) 中解决这个问题，一个根据第一个排序，另一个根据第二个排序。

代码有一些重复，我还没有费心清理。

#include <iostream>
#include <list>
#include <algorithm>
#include <tuple>
#include <any>

struct pair_and_iter {
    int first;
    int second;
    std::any other_iter;
};

struct compare_first {
    bool operator()(int x,pair_and_iter p){ return x < p.first; }
    bool operator()(pair_and_iter p, int x){ return p.first < x; }
};
struct compare_second {
    bool operator()(int x,pair_and_iter p){ return x < p.second; }
    bool operator()(pair_and_iter p, int x){ return p.second < x; }
};
template <typename Iter,typename Comp>
Iter my_find(Iter first,Iter last,int x, Comp comp) {
    auto it = std::lower_bound(first,last,x,comp);
    if (it != last && (!comp(x,*it) && !comp(*it,x))){
        return it;
    } else {
        return last;
    }
}

int main() {
    std::list<pair_and_iter> a {{0,1},{2,3},{1,6},{4,6},{8,9},{2,8}};
    std::list<pair_and_iter> b;

    for (auto it = a.begin(); it != a.end(); ++it){
        b.push_back({it->first,it->second,it});
        it->other_iter = std::prev(b.end());
    }

    a.sort([](const auto& x,const auto& y){ 
        return std::tie(x.first,x.second) < std::tie(y.first,y.second); });
    b.sort([](const auto& x,const auto& y){ 
        return std::tie(x.second,x.first) < std::tie(y.second,y.first); });
    
    std::vector<std::vector<pair_and_iter>> result;
    std::vector<pair_and_iter> current_result;
    current_result.push_back(a.front());
    auto current = current_result.begin();
    b.erase(std::any_cast<std::list<pair_and_iter>::iterator>(current->other_iter));
    a.erase(a.begin());        

    while (a.size() && b.size()) {
        // look for an element with same first
        auto it = my_find(a.begin(),a.end(),current->first,compare_first{});
        if (it == a.end()) {
            // look for element where current->second == elem.first
            it = my_find(a.begin(),a.end(),current->second,compare_first{});
        }
        if (it != a.end()){
            current_result.push_back(*it);
            current = std::prev(current_result.end());
            b.erase(std::any_cast<std::list<pair_and_iter>::iterator>(it->other_iter));
            a.erase(it);
            continue;
        }

        // look for element with current->first == elem.second
        it = my_find(b.begin(),b.end(),current->first,compare_second{});
        if (it == b.end()) {
            // look for element with same second
            it = my_find(b.begin(),b.end(),current->second,compare_second{});
        }
        if (it != b.end()) {
            current_result.push_back(*it);            
            current = std::prev(current_result.end());
            a.erase(std::any_cast<std::list<pair_and_iter>::iterator>(it->other_iter));
            b.erase(it);
            continue;
        }        
        // no matching element found
        result.push_back(current_result);
        current_result.clear();
        current_result.push_back(a.front());
        current = current_result.begin();
        b.erase(std::any_cast<std::list<pair_and_iter>::iterator>(current->other_iter));
        a.erase(a.begin());
    }
    result.push_back(current_result);
    for (const auto& chain : result){
        for (const auto& elem : chain){
            std::cout << elem.first << " " << elem.second << "\n";
        }
        std::cout << "\n";
    }
}

Output:

我使用了std::list，因为它有稳定的迭代器和常量时间擦除。 std::any 用于类型擦除，因为每个列表都包含指向另一个列表的迭代器。 a 相对于 first 排序，b 相对于 second 排序。因此 std::lower_bound 可用于在 O(logN) 中查找匹配项。单个线性搜索与 2 个二进制搜索进行交易以在 a 的 first 中查找 current->first 或 current->second 以及 2 个二进制搜索以查找 current->first 或current->second 在 second 中 b。总共是 O(N log(N)) 用于排序加上 O( log(N) + log(N-1) + log(N-2) + .... log(1)) 如果我没记错的话等于 O(log( n! ))。

PS: 你没说要找最长链，这个算法也不是找最长链。它只是选择剩余元素中的第一个元素，并使用它找到的下一个元素来继续链。

构建具有一个共同成员的数字对链

Construct chains of pairs of numbers with one common member

c++

sorting

algorithm

stl