229. Majority Element II

  • 28.0%

https://leetcode.com/problems/majority-element-ii/description/

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.

Hint:

  • How many majority elements could it possibly have?
  • Do you have a better hint? Suggest it!

还没有解决,需要学习下这个解法


https://discuss.leetcode.com/topic/17564/boyer-moore-majority-vote-algorithm-and-my-elaboration

Boyer-Moore Majority Vote algorithm and my elaboration

For those who aren’t familiar with Boyer-Moore Majority Vote algorithm,
I found a great article (http://goo.gl/64Nams) that helps me to understand this fantastic algorithm!!
Please check it out!

The essential concepts is you keep a counter for the majority number X. If you find a number Y that is not X, the current counter should deduce 1. The reason is that if there is 5 X and 4 Y, there would be one (5-4) more X than Y. This could be explained as “4 X being paired out by 4 Y”.

And since the requirement is finding the majority for more than ceiling of [n/3], the answer would be less than or equal to two numbers.
So we can modify the algorithm to maintain two counters for two majorities.

Followings are my sample Python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def majorityElement(self, nums):
if not nums:
return []
count1, count2, candidate1, candidate2 = 0, 0, 0, 1
for n in nums:
if n == candidate1:
count1 += 1
elif n == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = n, 1
elif count2 == 0:
candidate2, count2 = n, 1
else:
count1, count2 = count1 - 1, count2 - 1
return [n for n in (candidate1, candidate2)
if nums.count(n) > len(nums) // 3]

https://discuss.leetcode.com/topic/17396/boyer-moore-majority-vote-algorithm-generalization

Boyer-Moore Majority Vote algorithm generalization

Boyer-Moore Majority Vote algorithm generalization to elements appear more than floor(n/k) times

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> majorityElement(vector<int> &a) {
int y = 0, z = 1, cy = 0, cz = 0;
for (auto x: a) {
if (x == y) cy++;
else if (x == z) cz++;
else if (! cy) y = x, cy = 1;
else if (! cz) z = x, cz = 1;
else cy--, cz--;
}
cy = cz = 0;
for (auto x: a)
if (x == y) cy++;
else if (x == z) cz++;
vector<int> r;
if (cy > a.size()/3) r.push_back(y);
if (cz > a.size()/3) r.push_back(z);
return r;
}
};

https://discuss.leetcode.com/topic/17721/my-c-solution

My C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<int> majorityElement(vector<int>& nums) {
int cnt1 = 0, cnt2 = 0, a=0, b=1;

for(auto n: nums){
if (a==n){
cnt1++;
}
else if (b==n){
cnt2++;
}
else if (cnt1==0){
a = n;
cnt1 = 1;
}
else if (cnt2 == 0){
b = n;
cnt2 = 1;
}
else{
cnt1--;
cnt2--;
}
}

cnt1 = cnt2 = 0;
for(auto n: nums){
if (n==a) cnt1++;
else if (n==b) cnt2++;
}

vector<int> res;
if (cnt1 > nums.size()/3) res.push_back(a);
if (cnt2 > nums.size()/3) res.push_back(b);
return res;
}

https://discuss.leetcode.com/topic/23689/my-o-n-time-solution-20ms/3

My O(n) time solution ,20ms

My idea comes from Majority Vote algroithm,http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html.Now we vote two numbers simultaneously. if the next number is differents from them both.then the two numbers’ votes minus one. If some number’s vote comes zero,then vote the next number.Every time vote minus,it is the same that we remove the three numbers from the array.And the majority elemnts of original still are the majority elements in the end. So check t1 and t2 are the majority elements of original array at last.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> majorityElement(vector<int>& nums) {
int t1,t2,n1=0,n2=0; //numbers t1 and t2,votes' numbers n1,and n2.
for(int i=0;i<nums.size();++i)
{
if(n1!=0&&t1==nums[i]){++n1;continue;}
if(n2!=0&&t2==nums[i]){++n2;continue;}
if(n1==0){ t1=nums[i];++n1;continue;}
if(n2==0){ t2=nums[i];++n2;continue;}
--n1;--n2;
}
int z1=0,z2=0;
for(int i=0;i<nums.size();++i)
{
if(n1>0){ if(nums[i]==t1) ++z1;}
if(n2>0) {if(nums[i]==t2) ++z2;}
}
vector<int> ret;
//check t1 and t2.
if(z1>nums.size()/3) ret.push_back(t1);
if(z2>nums.size()/3) ret.push_back(t2);
return ret;
}

https://discuss.leetcode.com/topic/17409/6-lines-general-case-o-n-time-and-o-k-space

6 lines, general case O(N) time and O(k) space

Solution

I keep up to two candidates in my counter, so this fulfills the O(N) time and O(1) space requirements.

1
2
3
4
5
6
7
def majorityElement(self, nums):
ctr = collections.Counter()
for n in nums:
ctr[n] += 1
if len(ctr) == 3:
ctr -= collections.Counter(set(ctr))
return [n for n in ctr if nums.count(n) > len(nums)/3]

Explanation

Think of it this way: Find three different votes and hide them. Repeat until there aren’t three different votes left. A number that originally had more than one third of the votes now still has at least one vote, because to hide all of its votes you would’ve had to hide more than three times one third of the votes - more votes than there were. You can easily have false positives, though, so in the end check whether the remaining up to two candidates actually had more than one third of the votes.

My code does just that: Collect (count) the votes for every number, but remove triples of three different votes on the fly, as soon as we have such a triple.

Generalization to ⌊N/k⌋, still O(N) time but O(k) space

For the general problem, looking for elements appearing more than ⌊N/k⌋ times for some positive integer k, I just have to change my 3 to k. Then it already works and takes takes O(k) space and O(kN) time.

The O(kN) time does not come from the main loop, though. Yes, each ctr -= … does cost k, but I only have to do it at most N/k times. To put it in terms of the above explanation, I can’t hide a vote more than once.

No, the culprit is my last line, counting each remaining candidate separately. If I count them at the same time, I get O(N) again. Here’s the full generalized code:

1
2
3
4
5
6
7
8
def majorityElement(self, nums, k):
ctr = collections.Counter()
for n in nums:
ctr[n] += 1
if len(ctr) == k:
ctr -= collections.Counter(set(ctr))
ctr = collections.Counter(n for n in nums if n in ctr)
return [n for n in ctr if ctr[n] > len(nums)/k]

https://discuss.leetcode.com/topic/17473/c-solution-for-elements-appear-more-than-floor-n-k-times

C++ solution for elements appear more than floor(n/k) times

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> majorityElement(vector<int>& nums) {
return majorityElement(nums, 3);
}
vector<int> majorityElement(vector<int>& nums, const int k) {
const int size_n = nums.size();
vector<int> result;
unordered_map<int, int> cand;
for (int i = 0; i < size_n; i++) {
cand[nums[i]]++;
if (cand.size() == k) {
for (auto it = cand.begin(); it != cand.end(); ) {
if (--(it->second) == 0) it = cand.erase(it);
else it++;
}
}
}
for (auto& item : cand) item.second = 0;
for (auto& item : nums) {
if (cand.count(item) > 0) cand[item]++;
}
for (auto& item : cand) {
if (item.second > size_n / k) result.emplace_back(item.first);
}
return result;
}
谢谢你,可爱的朋友。