Solution to More Than Half Number from Jobdu

25 Aug

Question (in Chinese):

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 thoughts on “Solution to More Than Half Number from Jobdu

    • 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.

Leave a Reply

Your email address will not be published. Required fields are marked *