169. Majority Element

  • 45.4%

https://leetcode.com/problems/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.


方法一:

剑指offer 29

基于partition的解法

我的代码实现:

Oct 18, 2017

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
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
int l = 0, r = n-1;
int pos = partition(nums, l, r);
while(pos!=(n-1)/2){
if(pos > (n-1)/2){
r = pos - 1;
}else{
l = pos + 1;
}
pos = partition(nums, l, r);
}
return nums[pos];
}

int partition(vector<int>& nums, int l, int r){
if(l>=r)
return l;
int pos = l-1;
for(int i=l; i<r; i++)
if(nums[i]<nums[r])
swap(nums[i], nums[++pos]);
swap(nums[++pos], nums[r]);
return pos;
}
};

我的实现

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
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.empty()) return -1;
int n = nums.size();
int mid = n/2;
int left = 0, right = n-1;
int index = partition(nums, left, right);
while(index!=mid){
if(index<mid)
left = index+1;
else
right = index-1;
index = partition(nums, left, right);
}
return nums[mid];
}

int partition(vector<int>& nums, int left, int right){
if(left==right)
return left;
int pos = left-1;
for(int i=left; i<right; i++){
if(nums[i]<nums[right]){
swap(nums[i], nums[++pos]);
}
}
swap(nums[++pos], nums[right]);
return pos;
}
};

方法二:

根据数组特点找出O(n)的解法

我的实现

根据cnt是否为0,来分开。

cnt不为0,则就根据是否同于res来进行增减cnt。

我的代码实现:

Oct 18, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.empty()) return 0;
int n = nums.size();
if(n==1) return nums.back();
int res = nums[0], cnt = 1;
for(int i=1; i<n; i++){
if(cnt==0){
cnt = 1;
res = nums[i];
}else{
if(nums[i]==res)
cnt++;
else
cnt--;
}
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
if(n<=1) return nums[0];
int res;
int cnt = 0;
for(int i=0; i<n; i++){
if(cnt==0){
res = nums[i];
cnt = 1;
}else{
if(res == nums[i]){
cnt++;
}else{
cnt--;
}
}
}
return res;
}
};

https://discuss.leetcode.com/topic/8692/o-n-time-o-1-space-fastest-solution

O(n) time O(1) space fastest solution

使用一个cnt来表示个数,是个很不错的选择,当一样时增加, 不同时减少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int majorityElement(int[] num) {

int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;

}
return major;
}
}

https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations

6 Suggested Solutions in C++ with Explanations

Well, if you have got this problem accepted, you may have noticed that there are 7 suggested solutions for this problem. The following passage will implement 6 of them except the O(n^2) brute force algorithm.

Hash Table

The hash-table solution is very straightforward. We maintain a mapping from each element to its number of appearances. While constructing the mapping, we update the majority element based on the max number of appearances we have seen. Notice that we do not need to construct the full mapping when we see that an element has appeared more than n / 2 times.

The code is as follows, which should be self-explanatory.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
int n = nums.size();
for (int i = 0; i < n; i++)
if (++counts[nums[i]] > n / 2)
return nums[i];
}
};

Sorting

Since the majority element appears more than n / 2 times, the n / 2-th element in the sorted nums must be the majority element. This can be proved intuitively. Note that the majority element will take more than n / 2 positions in the sorted nums (cover more than half of nums). If the first of it appears in the 0-th position, it will also appear in the n / 2-th position to cover more than half of nums. It is similar if the last of it appears in the n - 1-th position. These two cases are that the contiguous chunk of the majority element is to the leftmost and the rightmost in nums. For other cases (imagine the chunk moves between the left and the right end), it must also appear in the n / 2-th position.

The code is as follows, being very short if we use the system nth_element (thanks for @qeatzy for pointing out such a nice function).

1
2
3
4
5
6
7
class Solution {
public:
int majorityElement(vector<int>& nums) {
nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
return nums[nums.size() / 2];
}
};

Randomization

This is a really nice idea and works pretty well (16ms running time on the OJ, almost fastest among the C++ solutions). The proof is already given in the suggested solutions.

The code is as follows, randomly pick an element and see if it is the majority one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
srand(unsigned(time(NULL)));
while (true) {
int idx = rand() % n;
int candidate = nums[idx];
int counts = 0;
for (int i = 0; i < n; i++)
if (nums[i] == candidate)
counts++;
if (counts > n / 2) return candidate;
}
}
};

Divide and Conquer

This idea is very algorithmic. However, the implementation of it requires some careful thought about the base cases of the recursion. The base case is that when the array has only one element, then it is the majority one. This solution takes 24ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int majorityElement(vector<int>& nums) {
return majority(nums, 0, nums.size() - 1);
}
private:
int majority(vector<int>& nums, int left, int right) {
if (left == right) return nums[left];
int mid = left + ((right - left) >> 1);
int lm = majority(nums, left, mid);
int rm = majority(nums, mid + 1, right);
if (lm == rm) return lm;
return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;
}
};

Moore Voting Algorithm

A brilliant and easy-to-implement algorithm! It also runs very fast, about 20ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int majorityElement(vector<int>& nums) {
int major, counts = 0, n = nums.size();
for (int i = 0; i < n; i++) {
if (!counts) {
major = nums[i];
counts = 1;
}
else counts += (nums[i] == major) ? 1 : -1;
}
return major;
}
};

Bit Manipulation

Another nice idea! The key lies in how to count the number of 1’s on a specific bit. Specifically, you need a mask with a 1 on the i-the bit and 0 otherwise to get the i-th bit of each element in nums. The code is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int majorityElement(vector<int>& nums) {
int major = 0, n = nums.size();
for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
int bitCounts = 0;
for (int j = 0; j < n; j++) {
if (nums[j] & mask) bitCounts++;
if (bitCounts > n / 2) {
major |= mask;
break;
}
}
}
return major;
}
};

https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation

Java solutions (sorting, hashmap, moore voting, bit manipulation).

1
2
3
4
5
// Sorting
public int majorityElement1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Hashtable 
public int majorityElement2(int[] nums) {
Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
//Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
int ret=0;
for (int num: nums) {
if (!myMap.containsKey(num))
myMap.put(num, 1);
else
myMap.put(num, myMap.get(num)+1);
if (myMap.get(num)>nums.length/2) {
ret = num;
break;
}
}
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// Moore voting algorithm
public int majorityElement3(int[] nums) {
int count=0, ret = 0;
for (int num: nums) {
if (count==0)
ret = num;
if (num!=ret)
count--;
else
count++;
}
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Bit manipulation 
public int majorityElement(int[] nums) {
int[] bit = new int[32];
for (int num: nums)
for (int i=0; i<32; i++)
if ((num>>(31-i) & 1) == 1)
bit[i]++;
int ret=0;
for (int i=0; i<32; i++) {
bit[i]=bit[i]>nums.length/2?1:0;
ret += bit[i]*(1<<(31-i));
}
return ret;
}

https://discuss.leetcode.com/topic/6251/c-solution-using-moore-s-voting-algorithm-o-n-runtime-comlexity-an-no-extra-array-or-hash-table

C++ solution using Moore’s voting algorithm - O(n) runtime comlexity an no extra array or hash table

This can be solved by Moore’s voting algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. Below code loops through each element and maintains a count of the element that has the potential of being the majority element. If next element is same then increments the count, otherwise decrements the count. If the count reaches 0 then update the potential index to the current element and sets count to 1.

1
2
3
4
5
6
7
8
9
10
11
12
int majorityElement(vector<int> &num) {
int majorityIndex = 0;
for (int count = 1, i = 1; i < num.size(); i++) {
num[majorityIndex] == num[i] ? count++ : count--;
if (count == 0) {
majorityIndex = i;
count = 1;
}
}

return num[majorityIndex];
}

https://discuss.leetcode.com/topic/6286/share-my-solution-java-count-bits

Share my solution [Java] - Count bits

Definitely not the fastest solution but I post it here for your reference since it’s different from the rest I saw. The problem reminded me of the approach I followed at Single Number II (problem 137).

We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially “construct” the number we look for.

The following code is simple and should be easy to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int majorityElement(int[] num) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int ones = 0, zeros = 0;
for (int j = 0; j < num.length; j++) {
if ((num[j] & (1 << i)) != 0) {
++ones;
}
else
++zeros;
}

if (ones > zeros)
ret |= (1 << i);
}
return ret;
}

https://discuss.leetcode.com/topic/7684/an-easy-way-to-solve-the-problem-24ms

An easy way to solve the problem ( 24ms )

Every number in the vector votes for itself, the majority number gets the most votes. Different number offsets the votes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int majorityElement(vector<int> &num) {

int vote = num[0];
int count = 1;
int size = num.size();
//vote from the second number
for( int i = 1; i < size; i++ )
{
if( count == 0 ) { vote = num[i]; count++; }
else if( vote == num[i] ) count++;
else count--;
}
return vote;
}

https://discuss.leetcode.com/topic/6287/one-line-solution-in-python

One line solution in Python

NOTICE that the majority element always exist in the array,so that the middle always is the answer

1
return sorted(num)[len(num)/2]
谢谢你,可爱的朋友。