Source url: https://leetcode.com/problems/majority-element/

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 exists in the array.

**Example 1:**

Input:[3,2,3]Output:3

**Example 2:**

Input:[2,2,1,1,1,2,2]Output:2

We provide 3 solutions. ** Hash-map** approach,

**approach and**

*divide and conquer***approach.**

*sort*## Hash-map approach

This solution is easily understood, we use a hash-map to store counts of elements. The first loop we count every element. The second loop we find the most frequency element, it is our result. Actually, we can use one loop to get the result, a little faster, but it will not change the complexity, so we ignore it.

## Divide and conquer approach

Because the majority element appears more than half times, so we know if we split the array to ** left** and

**, it will be one of the majority element in**

*right***or**

*left***. So we can use divide and conquer approach, cut again and again until only one element, just Mergesort problem.**

*right*## Sort approach

First, we sort the array, then one loop to count elements. (And there are a more easy solution, sort and get the middle element, it must be the majority element.)

Github address: https://github.com/tinyfool/leetcode/tree/master/src/p0169

Want to know details of the Divide and conquer, check my post: Leetcode problems of Divide and conquer.