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.
1 2 3 4 5 | Input: 9 1 2 3 2 2 2 5 4 2 Output: 2 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/25/2014 * Last updated: 08/25/2014 * * Filename: MoreThanHalfNumber.java * Compilation: javac MoreThanHalfNumber.java * Execution: java MoreThanHalfNumber * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * A utility to find the number in a given array, which appears more than half * of the array size. * @author Sheng Yu codesays.com */ public class MoreThanHalfNumber { /** * Find the number, which appear more than half of the input's size. * @param input the array to find. * @return the majority number if exist, or -1 otherwise. */ public int findMoreThanHalf(int[] input) { int count = 0; int number = -1; // Find an candidate, who might be the majority. for (int item : input) { if (count == 0) { number = item; ++count; } else { if (number == item) ++count; else --count; } } if (count == 0) { // No candidate. In other words, there is no majority number. return -1; } else { // Count the occurrence of the candidate number. count = 0; for (int item : input) { if (number == item) ++count; } // Check whether the candidate appears more than half times. if (count + count > input.length) return number; else return -1; } } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int arraySize = 0; int[] input = null; MoreThanHalfNumber finder = new MoreThanHalfNumber(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the test case. arraySize = (int) st.nval; input = new int[arraySize]; for (int i = 0; i < arraySize; ++i) { st.nextToken(); input[i] = (int) st.nval; } // Find the number, which appears more than half of the array size. System.out.println(finder.findMoreThanHalf(input)); } } } |
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.