数组中出现次数超过一半的元素
已关闭dadingPython / C++入场费 2 金币0 次提交
题目描述
给定一个长度为 n 的整数数组，找出其中出现次数超过 ⌊n/2⌋ 的元素。
你可以假设数组非空，且一定存在这样的元素。
要求时间复杂度 O(n)，空间复杂度 O(1)。
输入格式
第一行一个整数 n，表示数组长度（1 ≤ n ≤ 10^6） 第二行 n 个整数，表示数组元素（-10^9 ≤ ai ≤ 10^9）
输出格式
一行，一个整数，表示出现次数超过一半的元素
输入输出样例
样例 1
输入：
5 3 2 3 1 3
输出：
3
说明/提示
考虑 Boyer-Moore 投票算法