Ошибка SIGABRT (сигнал 6) при обнаружении элемента управления в массиве с использованием divide и conquer

Question

Я проверил SO и увидел два вопроса, касающихся одного и того же оператора проблемы. Однако ни один из них не содержал того, что я ищу. Задача состоит в том, чтобы вывести 1, если массив с элементами n содержит элемент, который встречается более чем n/2 раз, используя стратегию деления и завоевания .

Я разработал то, что, по моему мнению, является рабочим решением, основанным на том, что базовый регистр является вспомогательным массивом с одним элементом, который (очевидно) является элементом большинства в подмассиве. Затем я перехожу к сравнению этих элементов большинства в подмассивах, спрашивая, в конечном итоге они происходят больше, чем n/2 раз.

Для получения более подробной информации см https://classes.soe.ucsc.edu/cmps102/Fall01/solutions4.pdf (проблема 4)

Я написал два различных решения этой проблемы, один с использованием очень наивный O (N^2) алгоритм, чтобы проверить, что мое решение было правильным для всех случаев, и один пытается реализовать алгоритм, описанный в ссылке выше.

Внутри основного я подчеркиваю свое решение против явно правильного, но наивного. Однако, после запуска этого, я получаю ошибку SIGABRT (сигнал 6). Мой отладчик говорит мне проверить malloc, объект, вероятно, был изменен после освобождения.

Теперь я не могу сказать, правильно ли мое решение. Я действительно не знаю, что происходит с плохим распределением, я относительно новичок в C++.

Код опускается ниже:

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

using std::vector; 

int get_majority_element(vector<int> &a, int left, int right) { 


    int m; 
    int majority_left, majority_right;  // majority element in either sub array 
    int count_right = 0, count_left = 0; // count for above 
    int leftt, rightt;      // endpoints 

    if (a.size() == 1) { 
     return a[0]; 
    } 
    else { 

     m = (left + right)/2; // calculate mid point 

     vector<int> b_left(m); 
     vector<int> b_right(right - m); 


     // get left sub array 
     for (int i = 0; i < m; i++) { 
      b_left[i] = a[i]; 
     } 

     // set new endpoints 
     leftt = 0; 
     rightt = m; 

     majority_left = get_majority_element(b_left, leftt, rightt); 

     for (int i = 0; i < right - m + 1; i++) { 
      b_right[i] = a[m+i]; 
     } 

     leftt = m; 
     rightt = right - m + 1; 

     majority_right = get_majority_element(b_right, leftt, rightt); 

     // if there is a majority element, count its frequency 

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

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


     // if both elements in sub arrays are majority and they're different, there is no majority element 
     if (count_left == count_right && majority_left != majority_right) { 
      return -1; 
     } 

     // check if either sub array has a majority element that occurs more than n/2 times 
     else if (count_right > count_left && count_right > a.size()/2) { 
       return majority_right; 
     } 
     else if (count_left > count_right && count_left > a.size()/2){ 
      return majority_left; 
     } 
    } 

    return -1; 

} 


int get_majority_fast(vector<int> &a, int left, int right){ 

    std::reverse(a.begin(),a.end()); 

    int current = 0; 
    int count; 
    for (int i = 0; i < a.size(); i++) { 
     current = a[i]; 
     count = 0; 
     for (int j = 0; j < a.size(); j++) { 
      if (a[j] == current) 
       count ++; 
     } 
     if (count > a.size()/2) 
      return 1; 
    } 
    return -1; 
} 

int main() { 
// std::cin >> n; 
// vector<int> a(n); 
// for (size_t i = 0; i < a.size(); ++i) { 
//  std::cin >> a[i]; 
// } 
// std::cout << (get_majority_fast(a, 0, a.size()) != -1) << '\n'; 

    while(true){ 
     int one, two; 
     int n = rand() % 100 ; 
     std::cout << n << "\n"; 
     vector<int> a; 
     for (int i = 0; i < n; ++i) { 
      a.push_back(rand() % 100); 
     } 

     one = get_majority_element(a, 0, a.size()); 
     two = get_majority_fast(a, 0, a.size() != -1); 

     if (one != two) { 
      std::cout << "Wrong answer: " << one << ' ' << two << "\n"; 
      break; 
     } 
     else { 
      std::cout << "OK\n"; 
     } 
    } 
} 

Answer 1

Был фактически является из погрешности оценок в одной из петель. Корректированный контур находится ниже:

for (int i = m; i < right - m ; i++) { 
    b_right.at(m-i) = a.at(m + i); 
} 

Я думал, что странная ошибка SIGABRT вызвана чем-то тайным. Думаю, я научился использовать x.at()

Кроме того, у меня было еще несколько ошибок. Полный исправленный код ниже:

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


using std::vector; 

int get_majority_element(vector<int> &a, int left, int right) { 


    int m; 
    int majority_left = -1, majority_right = -1;  // majority element in either sub array 
    int count_right = 0, count_left = 0; // count for above 
    int new_left, new_right;      // endpoints 

    if (a.size() == 1) { 
     return a[0]; 
    } 
    else { 


     m = (a.size())/2; // calculate mid point 

     vector<int> b_left(m); 
     vector<int> b_right(right - m); 


     // get left sub array 
     for (int i = 0; i < m; i++) { 
      b_left.at(i) = a.at(i); 
     } 

     for (int i = 0; i < a.size() - m ; i++) { 
      b_right.at(i) = a.at(i + m); 
     } 

     // set new endpoints 
     new_left = 0; 
     new_right = m; 
     majority_left = get_majority_element(b_left, new_left, new_right); 


     new_left = m; 
     new_right = right - m; 

     majority_right = get_majority_element(b_right, new_left, new_right); 


     // if there is a majority element, count its frequency 

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

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


     // if both elements in sub arrays are majority and they're different, there is no majority element 
     if (count_left == count_right && majority_left != majority_right) { 
      return 0; 
     } 
     else if (count_left == count_right) 
      return majority_left; 
     // check if either sub array has a majority element that occurs more than n/2 times 
     else if (count_right > count_left && count_right > a.size()/2) { 
       return majority_right; 
     } 
     else if (count_left > count_right && count_left > a.size()/2){ 
      return majority_left; 
     } 
      // majority element in sub arrays isn't majority in array 
     else 
      return 0; 
    } 

} 


int get_majority_fast(vector<int> &a, int left, int right){ 

    std::reverse(a.begin(),a.end()); 

    int current = 0; 
    int count; 
    for (int i = 0; i < a.size(); i++) { 
     current = a[i]; 
     count = 0; 
     for (int j = 0; j < a.size(); j++) { 
      if (a[j] == current) 
       count ++; 
     } 
     if (count > a.size()/2) 
      return 1; 
    } 
    return -1; 
} 

int main() { 

    int n; 
    std::cin >> n; 
    vector<int> a(n); 

    for (size_t i = 0; i < a.size(); ++i) { 
     std::cin >> a[i]; 
    } 

    int result; 
    int out; 

    result = get_majority_element(a, 0, a.size()); 

    if (result != 0) 
     out = 1; 
    else 
     out = 0; 
    std::cout << out << '\n'; 


} 

Я уверен, что я мог бы сделать это намного симпатичнее, но сейчас я не хочу слышать об этом на некоторое время.