[Question Requirements] Give you n numbers and n. Now you need to find the number that occurs more than 50% of the times in the O(n) space within O(1).
[Start bullshit] At the beginning, I saw this question instantly blinded (ToT)/~~~(.*). If there is only the time requirement of O(n), it can be solved instantly with hash (that is, with space for time), and it seems difficult to solve the space of O(1).
[Thought 1] Double loop, this is the least efficient way to solve this problem, that is, calculate the number of times it appears for each number, and the time complexity O(n^2) is directly Out.
[Thought 2] First sort, let the similar numbers be arranged together, and then traverse from the first number. Now give an example, such as: 1000012, now sort: 0000112, start from 0, set a counter T=0, now there are 4 0s, then T=4, find that more than half of them, output 0. This method is the optimized version of the previous method, Out.
[Thought 3] It is the idea of exchanging space for time and hashing to make a one-dimensional array have two meanings. For example, a[x]=y represents that the number x appears y times. The time complexity of this method is O(n), but the space is really... I won't talk about it (* ￣￣) Out
[Thought 4] First calculate the probability, select the number of these numbers that are most likely to meet the requirements, and then randomly select a few. This... forget it.
[Thought 5] Today's topic is the so-called MJRTY algorithm, also known as the majority voting algorithm. The main ideas are as follows: (This algorithm's time complexity is O(n)! There is no need for extra storage in space, so the space complexity is O(1)!!!)
If count==0, set the value of vote to the current element of the array and assign count to 1;
Otherwise, if vote and now array elements have the same value, count++, otherwise count;
Repeat the above two steps until the array is scanned.
count is assigned to 0, and scan the array again from the beginning. If the value of the array element is the same as the value of vote, count++ until the array is scanned.
If the value of count is greater than or equal to n/2 at this time, the value of vote will be returned, otherwise -1 will be returned;
The following is the code implementation. Since the question ensures that the result must exist, we omitted the last step of checking and verification.
The key code is as follows:
#include<iostream>using namespace std;int len; void Find(int* a, int N) {char candidate;int nTimes, i;for(i=nTimes=0;i<N;i++){if(nTimes==0) candidate=a[i],nTimes=1;else{if(candidate==a[i]) nTimes++;else nTimes--;}}cout<<candidate; }int main(){cin>>len;int a[len];for(int i=0;i<n;i++) cin>>a[i];Find(a,len);system("pause");return 0;}The above is the number of more than half (50%) of the number of occurrences introduced to you by the editor. I hope it will be helpful to you. If you have any questions, please leave me a message and the editor will reply to you in time. Thank you very much for your support to Wulin.com website!