Given a sorted array, find how many times a specified element appears.

Question

v · Accepted Answer

I suppose "a specified element" means "a given value". "Specified element" normaly means "element with the given index", and there is only one such element. So, "find how many times a given value appears in a sorted array" would be the question to answer.

First, binary search yields _some_ element at _some_ index "j" with the given value in O(log(N)) time. Then step to the left and to the right from "j" till find values different from the given one. The number of steps is (K+1) where K is the number of elements with specified value.

The total computation time can vary between O(log(N)) and O(N) - the latter is when K is comparable to N

Naresh · Answer

One way it to do binary search and look left and right to find number of items.
Other way is to do two binary search. One establishes arr[i] =X and other etablishes arr[i]  X. The number of items is difference of these two indexes.    

public static int numEquals(int[] arr, int num) {
        if(arr.length = X 
        for(; i + 1 != j;){
            int k = (i + j) / 2;
            if (arr[k]  X
        if (arr[len-1] == num) return len - i;
        for(left = j, j = len; i + 1 != j;){
            int k = (i + j) / 2;
            if (arr[k] <= num) i = k; else j = k;
        }
        
        return j - left;
    }

Naresh · Answer

Minor correction above

  if(arr.length == 1){
            return arr[0] == num ? 1 : 0;
        }

Dan · Answer

One time, because is a sorted array.

Google

Domanda di colloquio di Google

Risposte di colloquio

Aziende seguite

Ricerche di lavoro