#### Problem Description:

- Condition: given a multiple set s Containing n elements, the number of times each element appears in S is called the multiplicity of the element. The element with the largest multiplicity in the multiple set s is called mode.

For example, S={1, 2, 2, 3, 5}. The mode of multiple set S is 2 and its multiplicity is 3. - Note that this multiple set is ordered, and the sorting algorithm is not examined
- Task: for a given multiple set s composed of n natural numbers, program to calculate the mode and multiplicity of S. It cannot be traversed completely at once.

#### data input

The input data consists of a file named input TXT text file. Number of elements in multiple sets S on line 1 of the file n; In the next N lines, each line has a natural number.

#### Result output

At the end of the program, the calculation results are output to the file output Txt. The output file has two lines, the first line gives the number of digits, and the second line is the number of duplicates.

#### Input and output samples

input.txt

6 1 2 2 2 3 5

output.txt

2 3

#### Train of thought analysis:

- First of all, traversal must not work. The time complexity is O (n). Combined with the divide and conquer idea of rigid learning, the large problem is decomposed into small problems.
- Common examples of divide and conquer algorithms are used to think, merge and sort, divide the overall long into short ones, and then divide the problem scale when merging and growing. The multiplication of large numbers is also the scale of the problem. Similarly, can this problem be considered from the perspective of the scale of the problem?
- For reference, through

#### Implementation code

#include <iostream> #include <fstream> #include <string> using namespace std; const int MAX_SIZE = 1000; /* Function: times is to return the number of times the number corresponding to the current index appears in the array num Parameter: num: array for recursion size: The actual size of the element participating in the comparison start，end: Is the starting paragraph of the left and right indexes involved in the comparison index: Is the index that gets the occurrence element up: Upper bound on the number of occurrences of an element down: Is the lower bound of the element */ void getTimes(int* num, int size, int& times, int index, int& up, int& down) { up = index - 1, down = index + 1; while (up >= 0) { //Traverse the left side of the target number if (num[up] == num[index]) { times++; up--; } //Develop launch conditions if (num[up] != num[index]) { break; } } while (down < size) { //Traverse the right side of the target number if (num[down] == num[index]) { times++; down++; } //Develop launch conditions if (num[down] != num[index]) { break; } } return; } /* Description: the process of recursion Parameter: num: array for recursion size: The actual size of the element participating in the comparison start，end: Is the starting paragraph of the left and right indexes involved in the comparison */ int getDivide(int* num, int size, int start, int end, int& value) { while (start < end) { //Count the current median times, and determine the starting point and end point of the corresponding comparison on the left and right sides int middle = (start + end) / 2, up = 0, down = 0, times = 1, compare = 0;//Times is the number of times the number corresponding to the middle appears. up is the lower limit on the left and down is the upper limit on the right int left = 0, right = 0;//Left and right here are used to save the maximum number of occurrences on the left and right sides getTimes(num, size, times, middle, up, down); value = num[middle]; //Determine whether recursion to the left and right sides is required if (times <= (up - start) + 1) { //Recursion of the left half left = getDivide(num, size, start, up, compare); if (left > times) { times = left; value = compare; } } //Determine whether recursion on the right is required if (times < (end - down) + 1) { //The right half is recursive right = getDivide(num, size, down, end, compare); //If the value of the right half is greater than times, replace it if (right > times) { times = right; value = compare; } } return times; } } /* Description: an external function called recursively. num is the original array and the actual length of the size array Parameter: num is the original array and the size of the size array Note: the last element of the array is used to hold the value with the most occurrences */ int RecursionOuter(int* num, int size) { int value = 0, times = 0; if (size == 0) { return 0; } else if (size == 1) { return 1; } else { times = getDivide(num, size - 1, 0, size - 2, value); num[size - 1] = value; return times; } } int main() { //Read in file ifstream infile; infile.open("data.txt"); //File exception if (!infile.is_open()) { cerr << "file cannot open!" << endl; return -1; } //Read in each line and use line to save the temporary string //index is used to save the corresponding array //Num is the corresponding array. The first item is the number of numbers in the file, followed by specific numbers string line; int index = 0, nums[MAX_SIZE]; while (!infile.eof()) { getline(infile, line); nums[index] = atoi(line.c_str()); index++; } infile.close(); //Data is to save the actual data //Size corresponds to the size of the array int data[MAX_SIZE] = { 0 },size = nums[0]; //Cout < < the number actually saved to it is < < endl; for (int i = 1; i < index;i ++) { data[i-1] = nums[i]; } //cout << "final result" << endl; cout << "Multiplicity:"<<RecursionOuter(data, size + 1) << endl; cout<<"Value:" << data[size] << endl; }

###### Analysis and summary:

- Looking at my code, I think I'm rubbish. My God, how can I write so long and complex? Modify it yourself, brother! I'm really uncomfortable. I'll show you someone else's. It's concise and more pleasing to the eye than a sister! Rare. I saw it for the first time. It's awesome to write C + + so simple.

Original link

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int>pi; const int maxn=1e5+100; const int N=1e6+100; const int M=1e5+100; const int mod=1e9+7; int n,m,T; int a[N]; int ans=0; //Multiplicity of mode int idx=0; //Subscript of mode void split(int l,int r) //Divide and conquer algorithm { if(l>r)return; int ll=l; //Record the original l position int rr=r; //Record the original r position int mid=(l+r)>>1; for(; l<mid&&a[l]!=a[mid]; l++); //Find the leftmost mode for(; r>mid&&a[r]!=a[mid]; r--); //Find the most right mode //After two for loops, the mode number is r-l+1 if(ans<=r-l+1) //Update answer { if(ans==r-l+1) { idx=min(mid,idx); } else idx=mid; ans=r-l+1; } if(l-1-ll+1>=ans) //prune split(ll,l-1); // Divide and conquer the left part if(rr-r-1+1>=ans) //prune split(r+1,rr); // Divide and conquer the right part } void solve() { scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",a+i); sort(a,a+n); //Sort first to facilitate the statistics of modes int l=0; int r=n-1; split(l,r); printf("%d %d\n",a[idx],ans); } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif solve(); }

###### Learn from

- About file input and output streams, this is great. It's much easier to import the contents of the file directly into the console!

freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);

- For those that may be used in recursion, use global variables to name them, and avoid confusing references and pointers, making yourself a little masked. The author sets the multiplicity and the corresponding value as global variables
- It's much more convenient to use pair control to return two values. Unlike me, it's too cumbersome to return two values with the last value of the array and the original return value
- make_pair constitutes a pair
- first and second to call related properties
- See connection for details

- If you want to use the algorithm package, don't write everything yourself. It's so hard

#### Analysis and summary

- Most of it is to rewrite this by yourself, because there are many places that are not clear, which is really a problem.