Solution to Number Of K from Jobdu

7 Sep

Question (in Chinese):

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.

The solution with binary search can guarantee O(logN) in the worst case.

Leave a Reply

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