Разделительные векторы в C++

Question

У меня есть некоторые значения в векторе и вы хотите их разбить (возможно, используя метод divide и conquer). Например, я хочу, чтобы иметь эту функцию:

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

Предполагая, что vectorIn содержит следующие значения: {5, 10, 15, 20, 25, 30, 25, 40};

Функция необходимо выполнить следующие действия:
1. Вычислить среднюю Е.Г. 21
2. Partition вектора в 2, а именно:

вектор А = {5, 10, 15, 20} // значения меньше среднего значения
вектор B = {25, 25, 30, 40} // значения больше среднего
3. Повторите то же самое для обоих векторов, пока мы не останемся с разделами с 2 или 1 векторами.

Выход для этого примера будет:

вектор А1: {5, 10};
вектор A2: {15, 20};
вектор B1: {25, 25};
вектор B2: {30};
вектор B3: {40};

Мой код выглядит следующим образом: // Первый и второй являются временные векторы ИНТ

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++. Я пробовал использовать алгоритм split и conquer, но пока не удался. Мои переменные повторно инициализируются, когда функция вызывается после первого раза. Кроме того, я должен иметь возможность динамически создавать векторы для хранения результата. Любая помощь или идеи о том, как реализовать это, будут высоко оценены. Спасибо

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; 
    } 

Сказав это, вы также можете сделать это с помощью массивов с вместо передачи массивов, проходящих только индексы.