Find count of a number in sorted array


  • 0
    M

    Int sorted array, with repeated numbers.
    Given a number K, return the count of K in the array
    e.g. 3, 5, 5, 5, 5, 7, 8, 8
    k = 6 return ->0
    k = 5 return ->4


  • 0
    U

    Use findLeft and findRight to get the left and right edge index of K, then
    the length of K is right - left + 1

    static int  findLeft(int[] A, int key) {
    		int len = A.length;
    		int b = 0;
    		int e = len - 1;
    		
    		while (b <= e) {
    			int mid = b + (e-b)/2;
    			
    			if (A[mid] == key) {
    				if (mid - 1 <= 0 || A[mid-1] < key) {
    					System.out.println(">>> left " + mid);
    					return mid;
    				} else {
    					e = mid - 1;
    				}
    			} else if (A[mid] < key) {
    				b = mid + 1;
    			} else { // A[mid] > key
    				e = mid - 1;
    			}
    		}
    		
    		return -1;
    	}
    
    static int  findRight(int[] A, int key) {
    		int len = A.length;
    		int b = 0;
    		int e = len - 1;
    		
    		while (b <= e) {
    			int mid = b + (e-b)/2;
    			
    			if (A[mid] == key) {
    				if (mid + 1 >= len || A[mid+1] > key) {
    					System.out.println(">>> right " + mid);
    					return mid;
    				} else {
    					b = mid + 1;
    				}
    			} else if (A[mid] < key) {
    				b = mid + 1;
    			} else { // A[mid] > key
    				e = mid - 1;
    			}
    		}
    		
    		return -1;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.