【问题描述】给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。题目保证一定存在多数元素。

【输入形式】输入的第1行中有1个数字n，表示数组的长度；第2行中有n个数字，表示数组的元素

【输出形式】输出1行一个数字表示该数组中的多数元素。
【样例输入】

3

1 2 1
【样例输出】

1

【说明】
1 <= n <= 10^5

-10^9 <= nums[i] <= 10^9

#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N];
int n;
int getcount(int l,int r,int x)
{int count=0;for(int i=l;i<=r;i++)if(q[i]==x)	count++;return count;
}
int solve(int l,int r)
{if(l>=r) return q[l];int mid=l+r>>1;int left=solve(l,mid);int right=solve(mid+1,r);if(left!=right){return getcount(l,mid,left)>=getcount(mid+1,r,right)?left:right;	}else return left;
}
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>q[i];int t=solve(1,n);cout<<t<<endl;return 0;
}