c++中的向量划分

Question

我在一个向量中有一些值，并想对它们进行分区（可能使用分治方法）。例如，我想有这个功能：

 vector<vector<int>> SplitVector(vector<int> vectorIn);

假设vectorIn包含以下值：{5，10，15，20，25，30，25，40}

该函数应执行以下操作：
1.计算平均值，例如21
2.将向量划分为2，即：

向量A={5，10，15，20}//值小于平均值
向量B=｛25，25，30，40｝//值大于平均值
3.对两个向量重复相同的操作，直到我们得到具有2或1个向量的分区

此示例的输出为：

向量A1:｛5，10｝
向量A2:{15,20}
向量B1:{25，25}
向量B2:{30}
向量B3:{40}

我的代码如下：//第一个和第二个是int 的临时向量

 vector<vector<int>> SplitVector(vector<int> vectorIn){
      int AVG = (int) std::accumulate(Input.begin(), vectorIn.end(), 0) / vectorIn.size();
      for(int i = 0; i <vectorIn.size(); i++){
           if(vectorIn.at(i) <= AVG){
                First.push_back(vectorIn.at(i));
           }else{
                Second.push_back(vectorIn.at(i));
           }
      }
      if(First.size() > 2){
           SplitVector(First); //use recursion if we have more than 2 element in vector
      }else{
           Result.push_back(First);
      }
      if(Second.size() > 3){
           SplitVector(First);
      }else{
           Result.push_back(Second);

      return Result;
 }

我正在用c++编程。我试着使用分治算法，但没有成功。在第一次调用函数后，我的变量将重新初始化。此外，我应该能够动态地创建向量来存储结果。如有任何关于如何实施这一计划的帮助或想法，我们将不胜感激。感谢

Answer 1

采用您定义的方法（可能不是最好的方法，因为您在递归中传递向量，对于较小的输入，不会影响效率）。这是一种伪代码

  vector<vector<int>> SplitVector(vector<int> vectorIn)
  {
       vector< vector<int> >left,right,result;
       vector<int>l,r;
       if(vectorIn.size() <= 2)
       {
            result.push_back(vectorIn);
            return result;
       }
       double average = 0;
       for(int i = 0;i < vectorIn.size();i++)
           average += vectorIn[i];
       average = average/(vectorIn.size());
       for(int i = 0;i < vectorIn.size();i++)
       {
           double num = (double)(vectorIn[i]*1.0);
           if(num > average)
               r.push_back(vectorIn[i]);
           else
               l.push_back(vectorIn[i]);
       }
       left = SplitVector(l);
       right = SplitVector(r);
       for(int i = 0;i < left.size();i++)
           result.push_back(left[i]);
       for(int i = 0;i < right.size();i++)
           result.push_back(right[i]);
       return result;
  }

话虽如此，您也可以使用的数组来实现这一点，而不是只传递索引的数组。