Several modes of numeric c ++

Question

I do assignments for the book by Bjarne Straustrup Programming: Principles and Practice Using C ++, 2nd Edition. At the head of 4, the task 16 it is necessary to find the mode of the number series. There were no problems with one mode, but what to do when there are several modes in a number series? For example, if in the row 4, 8, 8, 4, 9; fashion is the same and 4 and 8.

vector<double> numbers; for (double n; cin >> n;) numbers.push_back(n); sort(numbers); int counter = 0; for (int i = 0; i < numbers.size(); ++i) { for (int j = 0; j < numbers.size(); ++j) { if (numbers[i] == numbers[j]) ++counter; } //сколько каждое число повторяется раз arr.push_back(counter); counter = 0; } int n = 0; double max = 0; for (int i = 0; i < arr.size(); ++i) { if (arr[i] == 1) ++counter; if (arr[i] > max) { max = arr[i]; n = i; } } if (counter == arr.size()) cout << "We dont have mode\n"; else cout << "Mode: " << numbers[n] << '\n'; keep_window_open("~"); return 0;

Either record the modes also in a vector, or make two passes through the sequence: first look for the maximum repetition, and then output all values with the maximum repetition.

Accepted Answer · 2016-10-30T08:54:30

You have these cycles

 int counter = 0; for (int i = 0; i < numbers.size(); ++i) { for (int j = 0; j < numbers.size(); ++j) { if (numbers[i] == numbers[j]) ++counter; } //сколько каждое число повторяется раз arr.push_back(counter); counter = 0; }

not effective. Since the vector has already been sorted, it does not make sense to start the inner loop from the position equal to 0.

As for your question, there are several approaches. For example, you could write modes also in a vector. The second approach consists of two passes on a sorted vector. First, you find the maximum value of the repeated neighboring elements, and in the second pass, output those elements that are repeated the number of times found.

Below is a program that demonstrates the first approach using vector storage mod.

 #include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v = { 4, 8, 8, 4, 9 }; std::vector<int> mods; std::sort( v.begin(), v.end() ); using size_type = std::vector<int>::size_type; size_type max = 0; for ( size_type i = 0, j; i < v.size(); i = j ) { j = i + 1; while ( v[j] == v[i] ) ++j; if ( max <= j - i ) { if ( max != 1 ) { if ( max < j - i ) { max = j - i; mods.assign( 1, v[i] ); } else { mods.push_back( v[i] ); } } } } if ( max == 1 ) { std::cout << "We dont have mode\n"; } else { std::cout << "Mode" << ( mods.size() == 1 ? ":" : "s:" ); for ( int x : mods ) std::cout << ' ' << x; std::cout << '\n'; } return 0; }

Her console output is as follows.

 Modes: 4 8

I apologize, maybe I did not understand something, but if we take, for example, std :: vector <int> v = {3, 3, 8, 8, 4,4,4,4, 9};
, then the output of your algorithm will be 3.4, and it should be only 4. and I still haven’t really understood what is the meaning of the if (max <j - i) condition, if it is checked only if max was assigned to ji, you probably wanted to compare with the previous fashion value?
should be after the condition if (max <j - i) I corrected the code.

Harry Harry 106k 9 54 132 · Answer 2 · 2016-10-30T08:49:43

Output any :) - it will be a fashion. But let me give advice on how to proceed. You are now going through all the other numbers for each number encountered in the vector. Why, if the vector is already sorted ?

I would introduce two variables - the mode value and the number of its repetitions (initially - 0).

Further, going from the first value of the vector, I would simply count how many times the next value of the vector occurs (in your case - 4 4 8 8 9, then the first is 4, the second is 4, the third is not; stop. Current counter 0. It less received? yes. We are recording a new counter - 2, a new mode - 4. Continuing from the third element 8, fourth 8, fifth ... stop. Counter - 2. The recorded counter is less? No? ignore. (Or, if you check with using> = - then yes, overwrite counter 2, mode - 8). Continue from the fifth element. 9, the vector is over. Repetition is one, less is the account Ica, ignore.

So you will go through the vector only once. Otherwise, why did you sort it? :)

Majestio Majestio 2,917 one five 32 · Answer 3 · 2016-10-30T10:48:53

Here's another option, I will not say that it is optimal, but simple and visual:

 #include <unordered_map> #include <algorithm> #include <iostream> #include <vector> int main() { // -- вектор значений std::vector<int> Array = {7,5,3,2,2,4,5,7,9,0,1,1,4}; // -- карта частот std::unordered_map<int,int> Freq; for(auto &i:Array) Freq[i]++; // -- сортировка по частотам std::vector<std::pair<int, int>> Vec(Freq.begin(),Freq.end()); std::sort(Vec.begin(),Vec.end(),[](std::pair<int,int> a, std::pair<int,int> b) { return (a.second == b.second) ? a.first > b.first : a.second > b.second; }); // -- вывод пар по убыванию частот и по убыванию значений for(auto &i:Vec) std::cout << i.first << ":" << i.second << std::endl; // -- если нужен один элемент - возмем первый }

The output will be:

 7:2 5:2 4:2 2:2 1:2 9:1 3:1 0:1

Bogdan bogdan 85 eight · Answer 4 · 2016-10-31T13:16:38

I got another option.

 vector<int> repeats; vector<int> numbers = { 4, 8, 8, 4, 9 }; sort(numbers); int counter = 0; for (int i = 0; i < numbers.size(); ++i) { for (int j = 0; j < numbers.size(); ++j) { if (numbers[i] == numbers[j]) ++counter; } //сколько каждое число повторяется раз repeats.push_back(counter); counter = 0; } vector<int> num; vector<int> rep; for (int i = 0; i < repeats.size(); ++i) { //если счетчик равен кол-ву //значений в векторе - значит все числа //повторяются 1 раз и моды нет if (repeats[i] == 1) ++counter; //Удаление повторяющихся чисел и их повторов if (i == 0 || numbers[i - 1] != numbers[i]) { num.push_back(numbers[i]); rep.push_back(repeats[i]); } } int n = 0; int max = 0; for (int i = 0; i < num.size(); ++i) { if (rep[i] > max) { max = rep[i]; n = i; //индекс макимального кол-ва повторения } } cout << "\n"; if (counter == repeats.size()) cout << "We dont have mode\n"; else for (int i = 0; i < num.size(); ++i) //если максимальное повторение такое же выводим ещё моды if (rep[i] == rep[n]) cout << "Mode: " << num[i] << '\n';

Output to console:

 Mode: 4 Mode: 8

Several modes of numeric c ++

4 answers 4

More articles: