Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1349
Question Name: Number Of K
Question Description: count the occurrence of a number in a sorted integer arrray.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one integers N (1 <= N <= 1000000), saying the number of elements in the sorted integer arrays. The second line includes N integers as the content of the sorted array. The third line includes one integers M (1 <= N <= 1000), saying the number of queries. Each one of the following M lines contains one number as the query.
Output: for each query, print its occurrence in the sorted array.
1 2 3 4 5 6 7 8 9 | Input: 8 1 2 3 3 3 3 4 5 2 3 1 Output: 4 1 |
The solution with binary search can guarantee O(logN) in the worst case.
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 77 78 79 80 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/07/2014 * Last updated: 09/07/2014 * * Filename: NumberOfK.java * Compilation: javac NumberOfK.java * Execution: java NumberOfK * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * An utility to find the occurrence of a number in a sorted array. * @author Sheng Yu codesays.com */ public class NumberOfK { /** * Find the occurrence of the target number in the sorted array. * @param input the sorted integer array to find the target number * @param target the target number to find * @return the count of target in the array. */ public static int count(int[] input, int target) { int begin = 0, end = 0; // Find the begin position of target(s) in input, with binary search. int bs_begin = 0, bs_end = input.length - 1, bs_middle; while (bs_begin <= bs_end) { bs_middle = (bs_begin + bs_end) / 2; if (input[bs_middle] >= target) bs_end = bs_middle - 1; else bs_begin = bs_middle + 1; } if (bs_end + 1 >= input.length || input[bs_end + 1] != target) { // Did not find the target in the input array. return 0; } else { begin = bs_end + 1; } // Find the end position of target(s) in input, with binary search. bs_begin = begin; bs_end = input.length - 1; while (bs_begin <= bs_end) { bs_middle = (bs_begin + bs_end) / 2; if (input[bs_middle] > target) bs_end = bs_middle - 1; else bs_begin = bs_middle + 1; } end = bs_begin - 1; return end - begin + 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[] input = null; int inputSize = 0; while (st.nextToken() != StreamTokenizer.TT_EOF) { inputSize = (int) st.nval; input = new int[inputSize]; for (int i = 0; i < inputSize; ++i) { st.nextToken(); input[i] = (int) st.nval; } st.nextToken(); int queryCount = (int) st.nval; int query = 0; while (queryCount-- > 0) { st.nextToken(); query = (int) st.nval; System.out.println(count(input, query)); } } } } |