徐阳识主 · 众数破军

题目背景

徐阳击败云剑宗护山大阵后，大殿中一片狼藉。废墟之中，一枚上古传承玉简幽幽发光——

"仙帝遗诏：新任宗主由全体弟子投票产生。若有人得票严格超过半数，即为天命所归，继任宗主。"

徐阳拾起玉简，神识探入，发现其中记录了 N 位弟子的投票情况。投票记录杂乱无章，需要快速识别出谁才是真正的众望所归。

"超过半数……有意思。"徐阳嘴角微扬，指尖在玉简上轻轻一划。

题目描述

给定 T 组数据，每组包含一个整数 N 和一个长度为 N 的整数数组 nums，表示 N 位弟子的投票。数组中保证一定存在一个多数元素，即某个数字出现的次数 严格大于 （N/2）。

请找出这个多数元素。

输入格式

第一行一个整数 T，表示数据组数。

接下来对于每组数据：

• 第一行一个整数 N，表示数组长度。
• 第二行 N 个整数，以空格分隔，表示数组 nums。

输出格式

T 行，每行输出该组数据的多数元素。

样例

3
3
3 2 3
7
2 2 1 1 1 2 2
1
1

3
2
1

提示

你可以设计时间复杂度为 O(N)、空间复杂度为 O(1) 的算法吗？

（经典算法：Boyer-Moore 多数投票算法）

数据范围

• 1 ≤ T ≤ 4
• 1 ≤ N ≤ 10^5
• -10^9 ≤ nums[i] ≤ 10^9
• 保证每个测试数据中一定存在一个严格超过半数的多数元素
• 单组测试数据内所有 N 的总和不超过 10^5