改进解决方案

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();

我觉得可能会有一个使用组合器、或其他更简单的解决方案。我想了很多，什么都想不起来。所以我的要求是如果有人能改进解决方案。

Answer 1

正如上面提到的，如果不计算所有对的和，就很难做到这一点，所以我不打算处理这个问题，我只是提供关于有效数据结构的建议。

分析您的解决方案

您的代码预先添加了所有内容，然后对O(n^2)进行排序，然后删除重复项。但是由于你是从一个向量中擦除的，它最终将复杂性与元素的数量线性到列表的末尾。这意味着第二个循环将使算法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();
}