LeetCode 169. Majority Element and LeetCode 229. Majority Element II解题报告

LeetCode 169.Majority Element

Description:

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.

Difficulty:Easy

---

分析：

该题目要求寻找众数，且该数出现的次数不得少于⌊ n/2 ⌋，根据分析可知该数最多只有一个，而题目已保证存在一个符合要求的众数，因此可省略此判断。
接下来我们只需找出众数即可。先给任意数组从小到大排序，此时相等的数必定彼此相邻，因此比较相邻的数是否相等即可得出众数。

---

解答：

Solution #1和Solution #2大同小异，只在判断相等的数的个数有点区别，#1是比较cnt和max(=0)，而#2是比较cnt和(nums.size()-1)/2，从而造成了两者运行时间的差异，很明显#2快于#1。

Solution #1:(Run Time:26ms)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());// 排序
		int res = nums[0];
		int cnt = 0, max = 0;
		for (int i = 1; i < nums.size(); i++) {
			if (nums[i] == nums[i - 1]) {
				cnt++;
				if (cnt > max) {
					max = cnt;
					res = nums[i];
				}
			}
			else {
				cnt = 0;
			}
		}
		return res;
    }
};

---

Solution #2:(Run Time:23ms)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());// 排序
		int res = nums[0];
		int cnt = 0;
		for (int i = 1; i < nums.size(); i++) {
			if (nums[i] == nums[i - 1]) {
				cnt++;
				if (cnt >= (nums.size() - 1) / 2) {
					res = nums[i];
				}
			}
			else {
				cnt = 0;
			}
		}
		return res;
    }
};

---

改进：

经过一番搜索，得到了一种神奇的算法Boyer–Moore majority vote algorithm，也叫多数投票算法，时间O(n)，空间O(1)。采用该算法，可以把运行时间减小为22ms。

该算法的步骤如下：

• 如果cnt==0，则将vote的值设置为数组的当前元素，将cnt赋值为1；
• 否则，如果vote和当前数组元素值相同，则cnt++，反之cnt–；
• 重复上述步骤，直到遍历完数组。

Solution #3:(Run Time:22ms)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0;
		int vote;
		for (auto num : nums) {
			if (!cnt) vote = num;
			if (vote == num) cnt++;
			else cnt--;
		}
		return vote;
    }
};

---

Similar Questions:

---

LeetCode 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Difficulty:Medium

---

分析：

此题在前面的基础上加了一点要求，我们需要分析众数的可能个数，而时间空间的要求我们可以采用多数投票算法。
由于众数出现次数超过⌊ n/3 ⌋，根据观察可知，数组中最多有2个满足条件的众数。
由于题目中有限制时间和空间，所以我们根据多数投票算法来思考该问题。
思路：

• 两个候选众数：vote1和vote2，对应的出现次数为cnt1，cnt2，都赋值为0
• 遍历数组，记录当前数值为num
• 若num和vote1或者vote2相同，则将其对应的出现次数cnt1或者cnt2加一(cnt1++或者cnt2++)
• 否则，若cnt1或者cnt2为0，则将其赋值为1，对应的候选众数vote1或者vote2赋值为num
• 否则，将cnt1和cnt2分别减1
• 最后，统计候选众数在数组中出现的次数，若满足要求，则添加到vector中，返回结果。

---

Solution:(Run Time:12ms)

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
	    int cnt1 = 0, cnt2 = 0;
	    int vote1 = 0, vote2 = 0;
	    for (auto num : nums) {
		    if (num == vote1) cnt1++;
		    else if (num == vote2) cnt2++;
		    else if (!cnt1) cnt1 = 1, vote1 = num;
		    else if (!cnt2) cnt2 = 1, vote2 = num;
		    else cnt1--, cnt2--;
	    }
	    cnt1 = cnt2 = 0;
	    for (auto num : nums) {
		    if (num == vote1) cnt1++;
		    else if (num == vote2) cnt2++;
	    }
	    vector<int> ans;
	    if (cnt1 > nums.size() / 3) ans.push_back(vote1);
	    if (cnt2 > nums.size() / 3) ans.push_back(vote2);
	    return ans;
    }
};