169. 多数元素 ——【Leetcode每日一题】

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

$n == n u m s . l e n g t h$
$1 <= n <= 5 * 10^4$
$10^9 <= nums[i] <= 10^9$

进阶： 尝试设计时间复杂度为 $O (n)$ 、空间复杂度为 $O (1)$ 的算法解决此问题。

思路：(摩尔投票法)

法一：

先对数组排序，最中间那个数出现次数一定多于 n / 2。

法二：（进阶）

可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 $O (N)$ 。

算法可以分为两个阶段：

对抗阶段： 分属两个候选人的票数进行两两对抗抵消
计数阶段： 计算对抗结果中最后留下的候选人票数是否有效

可以这么理解该算法：

使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素 相等时，令 cnt++
当遍历到的元素和统计元素 不相等时：
- 如果前面查找了 i 个元素，且 cnt ！= 0，候选人 不变，cnt--；
- 如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2，因为如果多于 i / 2 的话 cnt 就一定不会为 0。遍历到下一个时，更换 候选人,且cnt = 1；
此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。
遍历完数组后，majority 即为最终答案。

代码：(Java、C++)

Java

import java.util.Arrays;public class MajorityElement {public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = {3,2,3};System.out.println(majorityElement(nums));}public static int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}

进阶：

public static int majorityElement(int[] nums) {int majority = nums[0], cnt = 0;for(int num : nums) {majority = cnt == 0 ? num : majority;cnt = majority == num ? ++cnt : --cnt;}return majority;
}

C++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class MajorityElement {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size() / 2];}
};int main() {MajorityElement m;vector<int> nums = {3,2,3};cout << m.majorityElement(nums) << endl;system("pause");return 0;
}

进阶：

class Solution {
public:int MajorityElement(vector<int>& nums) {int majority = nums[0], cnt = 0;for(int num : nums) {majority = cnt == 0 ? num : majority;cnt = majority == num ? ++cnt : --cnt;}return majority; }
};