- 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 | class Solution { |

我的实现

1 | class Solution { |

方法二：

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

我的实现

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

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

我的代码实现：

Oct 18， 2017

1 | class Solution { |

1 | class Solution { |

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

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

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

1 | public class Solution { |

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 | class Solution { |

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 | class Solution { |

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 | class Solution { |

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 | class Solution { |

Moore Voting Algorithm

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

1 | class Solution { |

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 | class Solution { |

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

1 | // Sorting |

1 | // Hashtable |

1 | // Moore voting algorithm |

1 | // Bit manipulation |

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 | int majorityElement(vector<int> &num) { |

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 | public int majorityElement(int[] num) { |

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 | int majorityElement(vector<int> &num) { |

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] |