Блог

Я решал проблему Majority_element, где мне будет предоставлен int ‘n’, за которым следует массив, размер которого равен n, в качестве входных данных. Если частота любого элемента в массиве больше n / 2, верните 1, в противном случае верните 0. Теперь моя программа корректно работает для небольших значений целых элементов, но выдает ложный вывод для больших значений int.

Вот исходный код

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

using std::vector;

int get_majority_element(vector<int> amp;a) {
  int count{};
  std::sort(a.begin(),a.end());
  for( size_t i{}; i<a.size() ;   i ){         //counter
    for( size_t j = i 1 ; j<a.size() ;   j ){
      if( a.at(i) == a.at(j) ){
        count  = 1;  // may have to inclue a count nullifier if two elements are repeated
      }
    }
  }
  if( count > ( a.size()/2 ) ){
    return 1;
  }
  else {
    return 0;  
  }

}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size();   i) {
    std::cin >> a.at(i);
  }
  std::cout << get_majority_element(a) << 'n';

  return 0;
}
  

Вот некоторые результаты

6

1 1 1 2 3 4

0

6

1 1 1 1 2 3

1

10

512766168 717383758 5 126144732 5 573799007 5 5 5 405079772

1 (должно быть 0)

Теперь кто-нибудь может объяснить мне, что происходит не так? Я даже попытался установить векторный тип данных на long long, чтобы предотвратить потенциальные утечки памяти.

Как вы делаете,

• вам не нужно std::sort .
• вам нужно выполнить сброс count .
• проверка должна выполняться во внешнем цикле

 bool get_majority_element(const vector<int> amp;a) {
  for (size_t i{}; i < a.size() ;   i) {
    int count{};
    for (size_t j = i 1 ; j<a.size() ;   j) {
      if (a.at(i) == a.at(j)){
        count  = 1;
      }
    }
    if (count > ( a.size()/2 )) {
      return true;
    }
  }
  return false;  
}
  

или

 bool get_majority_element(const vector<int> amp;a) {
    for (size_t i{}; i < a.size() ;   i) {
        if (std::count(a.begin()   i, a.end(), a[i]) > a.size() / 2) {
          return true;
        }
    }
    return false;  
}
  

Сложность: O(n²) .

После сортировки равные элементы соседствуют, поэтому вам не нужно проверять каждый элемент:

 bool get_majority_element(vector<int> amp;a) {
    std::sort(a.begin(), a.end());

    for (auto it = a.begin(); it != a.end(); /*empty*/) {
        auto next = std::find_if(it, a.end(), [amp;](int n){ return n != *it; });

        if (std::distance(it, next) > a.size() / 2) {
            return true;
        }
        it = next;
    }
    return false;  
}
  

Сложность: O(n lon n) .

Для информации существует также алгоритм для выполнения этого линейно, который заключается в поиске возможного кандидата, а затем его проверке.