分割と征服を使用して配列の多数の要素を見つける際のSIGABRT（シグナル6）エラー

Question

私はSOをチェックして、同じ問題文を扱う2つの問題を見た。しかし、どちらも私が探しているものを含んでいませんでした。 n要素の配列に、分割征服戦略を使用して、n/2回以上発生する要素が含まれている場合、1を出力することです。

私は、ベースケースが（明らかに）サブアレイ内の多数の要素である1つの要素を持つサブアレイであるという事実に基づいて、実際の解決策であると考えています。次に、サブアレイ全体でこれらの多数の要素を比較し、最終的にそれらがn/2回以上発生するかどうかを確認します。詳細については

、https://classes.soe.ucsc.edu/cmps102/Fall01/solutions4.pdf（問題点4）を参照してください

私は私の解決策は、すべてのケースのために正しかったかどうかを確認することは非常にナイーブO（N^2）のアルゴリズムを使用して、この問題に1を二つの異なる解決策を書きました、上記のリンクで説明したアルゴリズムを実装しようとするものです。

メインの中で、私は明らかに正しいが、ナイーブなものに対して私の解決策をテストします。しかし、これを実行すると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

ループの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'; 


} 

私はそれが多くきれい作ることができると確信しているが、今、私はしばらくの間、これについて聞きたくありません。