Given an array of integers, the majority number is the number that occurs <code>more than half</code> of the size of the array. Find it.
You may assume that the array is non-empty and the majority number always exist in the array.
Have you met this question in a real interview?
Example
Given <code>[1, 1, 1, 1, 2, 2, 2]</code>, return <code>1</code>
<a href="http://www.lintcode.com/en/problem/majority-number/#challenge">Challenge</a>
O(n) time and O(1) extra space
解法一：
解法二：