【LeetCode】169. Majority Element

问题描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

找出数组中个数超过了n/2个的元素。

注意：测试用例中数组不为空并且一定会出现Majority元素

思路

1. Hash表计数法：用一个Hash表记录每个元素出现的次数
2. Moore voting algorithm：记录元素elem，计数器counter，遍历数组，如果counter为0，则elem为当前元素；如果counter不为0，若elem==当前元素，counter++，若elem!=当前元素，counter--，最终的elem一定输Majority元素。因为一定会出现Majority元素，所以它的元素个数是大于n/2的，假设有k个，其余元素有m个，肯定有 k>m，所以最终计数下来，剩下的那个肯定是Majority元素

代码

1 Hash表计数法

class Solution {
public:

	int majorityElement(vector<int>& nums) {
		map<int, int> counts;
		for (int i = 0; i<nums.size(); i++) {
			if (counts.find(nums[i]) == counts.end()) {
				counts[nums[i]] = 0;
			}
			counts[nums[i]]++;
			if (counts[nums[i]]>nums.size() / 2) {
				return nums[i];
			}
		}
		return 0;
	}
}

2 Moore voting algorithm

class Solution {
public:

	int majorityElement(vector<int>& nums) {
		int count = 0;
		int elem = 0;
		for (int i = 0; i<nums.size(); i++) {
			if (count == 0) {
				elem = nums[i];
				count++;
			}
			else {
				if (elem == nums[i]) {
					count++;
				}
				else {
					count--;
				}
			}
		}
		return elem;
	}
}