1562. [算法课分治] 寻找多数

给定一个大小为 n 的整型数组 a,找到其中的多数元素,多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

输入

第一行输入一个整数 n \ (1 \leq n \leq 10^4) 代表数组的长度。

第二行输入一行数字代表数组 a \ (1 \leq a_i \leq 10^4),数字与数字之间用空格间开。

保证给定的数组总是存在多数元素。

输出

输出一个整数代表数组的多数元素。

样例

标准输入 复制文本
3
1 1 1
标准输出 复制文本
1
标准输入 复制文本
7
4 1 2 3 3 3 3
标准输出 复制文本
3
标准输入 复制文本
9
4 2 2 2 2 21 23 23 2
标准输出 复制文本
2

提示

如果数 a 是数组 n 的众数,如果我们将 n 分成两部分,那么 a 必定是至少一部分的众数。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 6056
通过 2981