I did it with two lines of code. As a result, my sister had a more ingenious way

Admit defeat Online .

Since I brought my sister's learning heart up , Her enthusiasm for learning never went down . see , Come to ah fan in the morning to discuss the algorithm .

sister ： Cute guy , Let me give you a question

Afan ： Come on , I don't believe it can be difficult for me

sister ： Given a size of n Array of , Find most of them . Most elements refer to the number of occurrences in an array greater than ⌊ n/2 ⌋ The elements of . You can assume that the array is not empty , And there are always many elements in a given array . such as ： Array [3,2,3] Most elements of are 3 , Array [2,2,1,1,1,2,2] Most elements of are 2 . What about? , You can answer it ？

Afan ： You really underestimate me .

Ah fan thought a little , Since most elements appear in the array more than ⌊ n/2 ⌋ , I'll put this array in order , Then take the middle value , The affirmation is that most elements , Otherwise, it does not conform to the meaning of the topic .

In this case , Two lines of code ：

​​java Arrays.sort(nums); return nums[nums.length >> 1];​​

After ah fan finished writing the program , There is nothing wrong with the operation , And two lines of code is done , Fan couldn't help being proud

Afan ： My little sister , I realized , Just two lines of code .

Sister looked , The result is a look of disgust ： Your code is simple , But the time complexity is O(nlogn) , The space complexity is O(logn) , There should be a better solution .

Helpless, ah fan thought like this at the beginning , So I can't think of any other good way , Go and ask my sister .

sister ： In fact, there is a better plan than yours , It's Moore voting . How do we usually vote ？ Everyone chooses one person to write on the note , Then he began to open the paper ball to see who he chose . At first, it was assumed that everyone was 0 ticket , Then who is on the note , This person has one more vote , Finally, it depends on who has more votes . Back to our topic , Since it is mode , And the number of occurrences is greater than ⌊ n/2 ⌋ , Then we can assume that a number is the required mode , At the same time, set the number of occurrences of this number to 0 , Then compare with the following figures . If it's the same , Let's add the number of times this number appears 1 , If it's not the same , Just reduce the number 1 , When this value is reduced to 0 when , Explain that the number assumed at the beginning is not a mode , Then change the current figure , Continue to cycle . In this way, the number of occurrences of the last number must be greater than or equal to 0 Of , Otherwise, it will not meet  ​​ Occurs more than ⌊ n/2 ⌋​​  This topic is meaningful , Last, last , Return the true mode .

Afan ： You say so , It opened my mind , You wait , I'm going to realize .

​​java // Set the initial number of votes to 0 int count = 0 ; // First define the required mode as null Integer majorityElement = null; // Circular array for(int num : nums){ // When count by 0 when , Suppose the current number is the required mode if (count == 0){ majorityElement = num; } // When num Equal to the assumed mode , count Just add 1 count += ( num == majorityElement ) ? 1 : -1 ; } // Finally, return the true mode return majorityElement;​​

Ah fan made a small calculation in his heart , It is found that the time complexity is O(n) , The space complexity is O(1) , Ah fan couldn't help but give her a big finger in her heart

Let a fan admit defeat online , Will you learn

< END >