Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller that the given integer.
Have you met this question in a real interview?
Yes
Example
For array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]
Note
We suggest you finish problem Segment Tree Build and Segment Tree Query II first.
Challenge
Could you use three ways to do it.
Tags Expand
Related Problems Expand
public class Solution { /** * @param A: An integer array * @return: The number of element in the array that * are smaller that the given integer */ public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) { // write your code here Arrays.sort(A); ArrayList<Integer> list = new ArrayList<Integer>(); for(Integer q : queries){ list.add(binarySearch(A,q)); } return list; } private int binarySearch(int[] A, int val) { int start = 0, end = A.length - 1; int res = 0; while (start <= end) { int mid = (start + end) / 2; if (A[mid] >= val) { end = mid - 1; } else { res = mid + 1; start = mid + 1; } } return res; } }