题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
题目解法
博耶-摩尔多数投票算法（英语：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素（出现次数超过一半的元素）的空间复杂度O(1)、时间复杂度O(n)算法。
该算法基于一个关键的观察：多数元素的出现次数大于其他所有元素出现次数之和。它通过一种“对抗抵消”的策略来工作：
- 将数组中的不同元素视为互相“抵消”。
- 由于多数元素的数量占绝对优势，无论怎么抵消，最后剩下的一定是多数元素。
通俗的说，可以将其想象成一场选举：
- 数组中的每个元素都是一张选票。
- 算法维护一个候选人（candidate）和该候选人当前的票数（votes）。
- 遍历过程中，支持当前候选人的票会增加票数，反对票则减少票数。
- 当票数归零时，意味着当前候选人没有任何优势，于是更换新的候选人。
- 由于多数元素的存在，最后获选的候选人一定是多数元素。
class Solution {public int majorityElement(int[] nums) {int n = nums.length;int candidate = 0, votes = 0;for (int i = 0; i < n; i++) {if (votes == 0) {candidate = nums[i];votes = 1;} else if (nums[i] == candidate) {votes++;} else {votes--;}}return candidate;}
}
