Given a target number and an integer array sorted in ascending order. Find the total number of occurrences of target in the array.
Example
Given [1, 3, 3, 4, 5]
and target = 3
, return 2
.
Given [2, 2, 3, 4, 6]
and target = 4
, return 1
.
Given [1, 2, 3, 4, 5]
and target = 6
, return 0
.
Challenge
Time complexity in O(logn)
先二分find the first,再count次数。切记find the first的话,if(target == mid){end = mid;}
public class Solution { /* * @param A: A an integer array sorted in ascending order * @param target: An integer * @return: An integer */ public int totalOccurrence(int[] A, int target) { // write your code here if (A == null || A.length == 0){ return 0; } // find the first target int start = 0; int end = A.length - 1; while (start + 1 < end){ int mid = start + (end - start) / 2; if (target <= A[mid]){ end = mid; } else { start = mid; } } int firstIdx = 0; if (A[start] == target){ firstIdx = start; } else if (A[end] == target){ firstIdx = end; } else { return 0; } // count the occurance int count = 0; for (int i = firstIdx; i < A.length; i++){ if (A[i] == target){ count++; } else { break; } } return count; } }