LeetCode-Majority Element II

た入场券 2022-08-03 12:40 131阅读 0赞

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.

此题是[Majority Element][]的继续，关于此题可以移步至[Majority Element][Majority Element 1]，关于Majority Element的解法挺多的，因为没有明确指明时间复杂度和空间复杂度，所以可以自由发挥，但是这个题就不那么随意了。可以看[Majority Element][Majority Element 1]的最好一个解法，基于Boyer-Moore Algorithm。

先温习下上一题。此种算法的主要思想就是成组的出现，然后同时删除两个不相等的数，最后剩下的肯定是Majority Element。

比如Majority Element问题，可以分两种情况，Majority Element是否在此被消除的分组中

1）如果让Majority Element和其他非此元素成对的删除，显然最后剩下的就是Majority Element，因为这个元素是多数的。这显然是最坏的情况

2）如果两个非Majority Element元素成对被删除，那剩下的Majority Element数量会更多。

而以上两种中，如果被假定的元素的counter为0，说明此元素是被消除者，非Majority Element，所以要交换假定的Majority Element。

\----------------------------------------------------------------------------------------------------------------

再来搞这一题，通过分析此题可以得知，满足这个条件的元素最多为两个，所以这次就可以以三个为一组：  
1）当前元素与假定Majority Element相等时，计数器加1。

2）当当前元素的计数器为0是，说明是被消除者，交换假定的Majority Element。

3）如果与假定的Majority Element不相等时，同时消除一组，此时为3个元素，即消除两个假定的Majority Element，两个计数器同时减1。

4）最后不要忘记判断得出来的元素是否为Majority Element

根据以上分析，可以得出如下代码：

public List<Integer> majorityElement(int[] nums) {
            List<Integer> ret = new ArrayList<Integer>();
            if (nums == null || nums.length == 0) return ret;
            int num1 = 0, num2 = 0, cnt1 = 0, cnt2 = 0;
            for (int i = 0; i < nums.length; i++) {
            	if (num1 == nums[i]) cnt1++;
            	else if (num2 == nums[i]) cnt2++;
            	else if (cnt1 == 0) {
            		cnt1++;
            		num1 = nums[i];
            	} else if (cnt2 == 0) {
            		cnt2++;
            		num2 = nums[i];
            	} else {
            		cnt1--;
            		cnt2--;
            	}
            }
            cnt1 = 0;
            cnt2 = 0;
            for (int i = 0; i < nums.length; i++) {
            	if (num1 == nums[i]) cnt1++;
            	else if (num2 == nums[i]) cnt2++;
            }
            if (cnt1 > nums.length/3) ret.add(num1);
            if (cnt2 > nums.length/3) ret.add(num2);
            return ret;
        }

这种题可以提升到满足 ⌊ n/k ⌋

[Majority Element]: https://leetcode.com/problems/majority-element/
[Majority Element 1]: http://blog.csdn.net/my_jobs/article/details/43191665