# Solution to More Than Half Number from Jobdu

25 Aug

Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1370

Question Name: More Than Half Number

Question Description: Give an integer array, there might be one number, which appears more than half times. If it exists, find out it. For example, in the array {1,2,3,2,2,2,5,4,2}, 2 appears 5 times, that is greater than half of the array length (4). And we want to find out 2.

Input: the input might contain multiple test cases. Each test case includes two lines. The first line is an integer N (1<=n<=100000), saying the size of the given array. The next line includes N integers as the content of the array.

Output: For each test case, print the majority number if it exist, or -1 otherwise.

The solution is:

### 2 Replies to “Solution to More Than Half Number from Jobdu”

• Sheng says:

This solution is working, but have some space to improve. Its time complexity is the same as mine in average, but worse in worst case. And it needs O(N) space.