改进解决方案

Question

一个任务的描述是这样的：
我们有 n 个数字，我们必须找到数组中所有对的唯一总和的数量。
例如：

3 2 5 6 3  
The sums of all the pairs(non-repeated) are 5 9 8 6 8 7 5 11 9 8  
Unique are 5 9 8 6 7 11  
Therefore output is 6

我想出了这个非常原始且耗时（意味着复杂性）的解决方案：

int n = 0;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vec[i];
    }
    vector<int> sum;
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            sum.push_back(vec[i] + vec[j]);
        }
    }
    sort(sum.begin(), sum.end());
    for (int i = 0; i < sum.size()-1;)
    {
        if (sum[i] == sum[i + 1]) sum.erase(sum.begin() + i);
        else i++;
    }
    cout << endl << sum.size();

我觉得可以使用 Combinatorics 或更简单的方法来解决。我想了很多，也想不出什么。所以我的要求是，是否有人可以改进解决方案。

Answer 1

如上所述，如果不计算所有对的总和，很难做到这一点，所以我不会处理这个问题，我只是想就高效的数据结构提出建议。

分析你的解决方案

您的代码预先添加所有内容 O(n^2) 然后排序 O(n^2 log(n))，然后删除重复项。但是由于您是从向量中删除的，因此最终 complexity 与列表末尾的元素数量呈线性关系。这意味着第二个循环将使你的算法复杂度O(n^4).

您可以在不删除的情况下计算排序数组中的唯一元素

int count = 0;
for (int i = 0; i < sum.size()-1; ++i)
{
        if (sum[i] != sum[i + 1]) ++count
}

仅此一项更改就使您的算法变得复杂 O(n^2 log n)。

没有排序的备选方案。

这里有替代方案 O(n^2) 和存储取决于输入值的范围而不是向量的长度（最后一个除外）。

我正在测试 1000 个小于 0 到 10000 的元素

vector<int> vec;
for(int i = 0; i < 1000; ++i){
    vec.push_back(rand() % 10000);
}

您的实施sum_pairs1(vec)（18 秒）

int sum_pairs1(const vector<int> &vec){
    vector<int> sum;
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            sum.push_back(vec[i] + vec[j]);
        }
    }
    sort(sum.begin(), sum.end());
    for (int i = 0; i < sum.size()-1;)
    {
        if (sum[i] == sum[i + 1]) sum.erase(sum.begin() + i);
        else i++;
    }
    return sum.size();
}

如果您知道值总和的范围，则可以使用位集，从而有效地使用内存 sum_pairs2<20000>(vec)（0.016 秒）。

template<size_t N>
int sum_pairs2(const vector<int> &vec){
    bitset<N> seen;
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            seen[vec[i] + vec[j]] = true;
        }
    }
    return seen.count();
}

如果你知道最大总和不是那么高（向量不是很稀疏），但你不知道在编译时你可以使用向量，你可以跟踪最小值和最大值来分配最小可能值，也支持负值。

int sum_pairs2b(const vector<int> &vec){
    int VMAX = vec[0];
    int VMIN = vec[0]
    for(auto v : vec){
        if(VMAX < v) VMAX = v;
        else if(VMIN > v) VMIN = v;
    }
    vector<bool> seen(2*(VMAX - VMIN) + 1);
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            seen[vec[i] + vec[j] - 2*VMIN] = true;
        }
    }
    int count = 0;
    for(auto c : seen){
        if(c) ++count;
    }
    return count;
}

并且如果您想要一个适用于稀疏数据的更通用的解决方案sum_pairs3<int>(vec)（0.097 秒）

template<typename T>
int sum_pairs3(const vector<T> &vec){
    unordered_set<T> seen;
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            seen.insert(vec[i] + vec[j]);
        }
    }
    return seen.size();
}

改进解决方案

Improving a solution

c++

vector

combinatorics

分析你的解决方案

没有排序的备选方案。