一、题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3] 输出3示例 2输入nums [2,2,1,1,1,2,2] 输出2提示1 n 5 * 10^4 -10^9 nums[i] 10^9进阶要求时间复杂度 O(n) 空间复杂度 O(1)二、解题思路摩尔投票法这道题的最优解是Boyer-Moore Voting Algorithm摩尔投票法。核心思想如果一个元素出现次数大于 n/2那么它的数量一定比所有其他元素数量之和还多。因此我们可以让不同元素互相抵消最后剩下的一定是多数元素。算法步骤维护两个变量candidate 当前候选人 count 计数遍历数组① 当 count 0说明之前元素已经全部抵消当前元素成为新的候选人candidate nums[i]② 如果元素相同count③ 如果元素不同count--表示两个不同元素相互抵消三、过程示例数组nums [2,2,1,1,1,2,2]遍历过程元素candidatecount说明221新候选222相同 1121抵消120抵消111新候选210抵消221新候选最终候选人2四、C语言实现int majorityElement(int* nums, int numsSize) { int candidate 0; int count 0; for(int i 0; i numsSize; i) { if(count 0) { candidate nums[i]; } if(nums[i] candidate) { count; } else { count--; } } return candidate; }五、复杂度分析时间复杂度O(n)只需要遍历数组一次。空间复杂度O(1)只使用了常数变量。六、为什么摩尔投票法一定正确因为多数元素数量 n/2设多数元素数量 m 其他元素数量 k则m k在不断进行两两抵消时m - k 0因此最后留下的一定是多数元素。七、其他解法了解1 Hash表统计统计每个元素出现次数。时间复杂度O(n)空间复杂度O(n)2 排序法排序后nums[n/2]一定是多数元素。时间复杂度O(n log n)空间复杂度O(1)八、总结方法时间复杂度空间复杂度Hash表O(n)O(n)排序O(n log n)O(1)摩尔投票法O(n)O(1)摩尔投票法是本题最优解也是面试高频算法。