描述
給一個(gè)升序的數(shù)組，以及一個(gè) target衫冻，找到它在數(shù)組中出現(xiàn)的次數(shù)。
樣例
給出 [1, 3, 3, 4, 5] target = 3, 返回 2.
給出 [2, 2, 3, 4, 6] target = 4, 返回 1.
給出 [1, 2, 3, 4, 5] target = 6, 返回 0.
標(biāo)簽
二分法
相關(guān)題目
搜索區(qū)間
代碼實(shí)現(xiàn)
public class Solution {
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
public int totalOccurrence(int[] A, int target) {
if (A == null || A.length == 0) {
return 0;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
int count = 0;
if (A[start] == target) {
for (int i = start; i < A.length; i++) {
if (A[i] == target) {
count++;
}
}
return count;
}
if (A[end] == target) {
for (int i = end; i < A.length; i++) {
if (A[i] == target) {
count++;
}
}
return count;
}
return 0;
}
}
