c++ - 查找具有 n 个 int 类型元素的 3 个向量的出现次数最多的总和

Question

我有 n 个带有 k 个 int 类型元素的向量。将这些 n 个向量中包含的所有元素组合相加时，如何找到出现次数最多的总和？

目前正在处理具有 3 个向量的样本：

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <limits>

int main()
{
    std::vector<int> v;
    std::vector<int> x;
    std::vector<int> y;
    std::vector<int> mostCommon;
    int inputV;
    int inputX;
    int inputY;

    std::cout << "Enter values for vector v: ";
    while (std::cin >> inputV)
    {
       v.push_back(inputV);
    }
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

    std::cout << "Enter values for vector x: ";
    while (std::cin >> inputX)
    {
       x.push_back(inputX);
    }
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

    std::cout << "Enter values for vector y: ";
    while (std::cin >> inputY)
    {
       y.push_back(inputY);
    }

    std::vector<int> possibleSums;

    for( int vE : v )
        for( int xE : x )
            for( int yE : y )
                possibleSums.push_back( vE + xE + yE );

    std::sort( possibleSums.begin(), possibleSums.end() );
    std::set<int> possibleSumSet( possibleSums.begin(), possibleSums.end() );

    int mostCommonCount = 0;
    for( int sum : possibleSumSet )
    {
        int count = std::count( possibleSums.begin(), possibleSums.end(), sum );
        if( count >= mostCommonCount )
        {
            mostCommonCount = count;
            mostCommon.push_back (sum);
        }
    }

    std::cout << "Most Common Sum Range: " << int(mostCommon.size()) << std::endl;
    std::cout << "Most Common Sums: ";
    for (auto i = mostCommon.begin(); i != mostCommon.end(); ++i)
    {
        std::cout << *i << ' ';
    }
    std::cout << std::endl << "Most Common Count: " << mostCommonCount;
}

---

向量的样本输入：

Enter values for vector v: 1 2 4 5
Enter values for vector x: 1 2 3
Enter values for vector y: 2 3

以上样本输入的可能总和：

1+1+2=4  
1+1+3=5  
1+2+2=5  
2+1+2=5  
1+2+3=6  <-  
1+3+2=6  <-  
2+1+3=6  <-  
2+2+2=6  <-  
1+3+3=7  <-   
2+2+3=7  <-  
2+3+2=7  <-  
4+1+2=7  <-  
2+3+3=8  <-  
4+1+3=8  <-  
4+2+2=8  <-  
5+1+2=8  <-  
4+2+3=9  <-  
4+3+2=9  <-  
5+1+3=9  <-  
5+2+2=9  <-   
4+3+3=10  
5+2+3=10  
5+3+2=10  
5+3+3=11 

所以这里的结果是：

• 最常见的总和范围：4
• 最常见的数字：6、7、8、9
• 最常见的计数：4

我目前得到的是：

Most Common Sum Range: 6                                                                                                    
Most Common Sums: 4 5 6 7 8 9                                                                                               
Most Common Count: 4 

标签： c++

Answer 1

最简单的方法是只循环最大的向量，为每个向量的每个元素循环每个较小的向量，将它们所有的结果推送到一个新的向量，并找到最常见的向量，即

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v = { 1, 2, 4, 5 };
    std::vector<int> x = { 1, 2, 3 };
    std::vector<int> y = { 2, 3 };

    std::vector<int> possibleSums;

    for( int vE : v )
        for( int xE : x )
            for( int yE : y )
                possibleSums.push_back( vE + xE + yE );

    std::sort( possibleSums.begin(), possibleSums.end() );
    std::set<int> possibleSumSet( possibleSums.begin(), possibleSums.end() );

    int mostCommon = 0, mostCommonCount = 0;
    for( int sum : possibleSumSet )
    {
        int count = std::count( possibleSums.begin(), possibleSums.end(), sum );
        if( count > mostCommonCount )
        {
            mostCommonCount = count;
            mostCommon = sum;
        }
    }

    std::cout << "Most Common Sum: " << mostCommon 
              << "; Most Common Count: " << mostCommonCount;
}

编辑：您还可以将每个最高出现的数字存储到一个std::vector因此后续最高出现不会被忽略：

int mostCommonCount = 0;
std::vector<int> mostCommonSums;
for( int sum : possibleSumSet )
{
    int count = std::count( possibleSums.begin(), possibleSums.end(), sum );
    if( count > mostCommonCount )
    {
        mostCommonCount = count;
        mostCommonSums.clear();
        mostCommonSums.push_back( sum );
    }
    else if( count == mostCommonCount )
    {
        mostCommonSums.push_back( sum );
    }
}

for( int sum : mostCommonSums )
    std::cout << "Most Common Sum: " << sum << std::endl;

std::cout << "Most Common Count: " << mostCommonCount;