Title Description

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 .
The array is not empty , And there are always many elements in a given array .

Example 1：

 Input ：[3,2,3]
 Output ：3

Example 2：

 Input ：[2,2,1,1,1,2,2]
 Output ：2

Their thinking

   There are two solutions to this problem , But the time complexity of the two methods is one order of magnitude different , Readers should compare the differences between the two methods , Especially the subtlety of the second method .

  Method 1： Using the idea of sorting

 This idea is what most people can think of , It is also the one with the least number of lines of code , But it will take advantage of STL Provided in the standard template library sort() function ,
 For beginners, it is recommended to use this method directly API Of , Will limit your thinking , To do algorithm problems is to cultivate ideas . This solution time 
 The complexity is about O（nlogn）.

int majorityElement(vector<int>& nums) {
    
	sort(nums.begin,nums.end);
	return nums[nums.size()/2];
	}

  Method 2： Start with the first number count=1, In case of the same, add 1, In case of different, reduce 1, Reduced to 0 Just change the number and start counting , Always find the most . You'd better simulate it manually , Experience the subtlety of this solution , Deepen the impression . Time complexity O(n)

int majorityElement(vector<int>& nums) {
    
	int count=1;
	int flag=nums[0];
	for(int i=1;i<nums.size();i++)
	{
    
		if(flag==nums[i])
			count++;
		else{
    
			count--;
			if(count==0)
				flag=nums[i+1];
		}
	}
	return flag;
}