Даны m наборов из n элементов. Найдите элемент, который встречается в максимальном количестве наборов в C ++.

Question

Учитывая m наборы n целых чисел, которые содержат n элементов, найдите элемент, который встречается в максимальном количестве наборов Не максимальное количество раз .

Вот алгоритм, который я реализовал.

• сканировать входы один за другим
• Для каждого элемента значение счетчика увеличивается. этот счетчик показывает частоту появления в наборах, не входящих в наборы. Надеюсь, здесь все понятно
• Вывод максимального элемента из count max(count)

 int main(){
   set <int> inner1;      //Here ,I have implemented just 2 sets 
   set <int> inner2;      
   set< set<int> > outer;      //a set of sets                 
   set< set<int> >:: iterator new_it;
   set<int >::iterator it;
  map <int ,int> count;  //the counter

   cout<<"enter the number of sets"<<endl;
   cin>>m;
   cout<<"enter the number of elements in each set"<<endl;
   cin>>n;
   for (int i=0;i<n;i++){
     int temp;
     inner1.insert(temp);
   }
   for (int i=0;i<n;i++){
     int temp;
     inner2.insert(temp);
   }
   outer.insert(inner1);       // a set of two sets .
   outer.insert(inner2);


  for (){
  for (){
    // THe MAIN CODE 
   
 }

Мой вопрос-

1. Я хочу реализовать его таким образом, чтобы он мог создавать m sets in a set с вводом пользователя. Я попытался реализовать это как 2 набора на данный момент, но как я могу реализовать его для m наборов в соответствии с wi пользователя sh.

cout<<"enter the number of sets"<<endl;
cin>>m;
cout<<"enter the number of elements in each set"<<endl;
cin>>n;

Надеюсь, вы уловили суть

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

Заранее спасибо.

Answer 1

Я просто напишу код, поскольку его легко понять:

unordered_map<int, int> global;

for(set<int> &s : sets){   //for each set you have
    for(int si : s) {      //for each element of the set (all unique by definition)
        global[si]++;
    }
}

int mostFrequent = *sets[0].begin();   //any existing element in any set is allowed
int frequency = global[mostFrequent];
for (auto& it: global) {              //for each element in all sets
    if(it.second > frequency) {
        mostFrequent = it.first;
        frequency = it.second;
    }
}

cout<<"answer is "<<mostFrequent<<endl;

Ваш вопрос немного странный в том смысле, что set по определению не будет иметь повторяющихся элементов в это, поэтому нет смысла подчеркивать, что вам не нужен элемент, который встречается « максимальное количество раз », поскольку это происходит непосредственно из определения set, что этот элемент будет таким же, как элемент, который встречается в максимальном количестве наборов .

Если вы имеете в виду set, которые разрешают повторяющиеся элементы, вы должны использовать vector или list. В этом случае решением было бы преобразовать такую ​​структуру в set.

Answer 2

@ Daniel Вы также можете «накапливать» результат (так как std :: accumulate можно использовать для всего)

using pint = std::pair<int, int>;
auto res = std::accumulate(count.begin(), count.end(), pint(0,0), 
    [](const auto& e1, const auto& e2) { return e1.second > e2.second ? e1 : (pint)e2; 
  }
);

https://godbolt.org/z/fha8v8