Total Occurrence of Target.png
===================== 解題思路 =====================
分開兩次找出最先出現跟最後出現的 target 之 index 然後相減再 + 1 得到答案 過程可參考 First Position of Target (找最先出現 反過來做可得到最後出現)
===================== C++ code ====================
<pre><code>
class Solution {
public:
/**
* @param A an integer array sorted in ascending order
* @param target an integer
* @return an integer
*/
int totalOccurrence(vector<int>& A, int target) {
// Write your code here
int n = A.size();
if(n == 0) return 0;
int small = 0, large = n - 1;
int left = 0, right = n - 1;
if(A[left] > target || A[right] < target) return 0;
while(left + 1 < right)
{
int mid = left + (right - left) / 2;
if(A[mid] >= target) right = mid;
else left = mid;
}
if(A[left] != target && A[right] != target) return 0;
if(A[left] == target) small = left;
else if(A[right] == target) small = right;
left = 0;
right = n - 1;
while(left + 1 < right)
{
int mid = left + (right - left) / 2;
if(A[mid] > target) right = mid;
else left = mid;
}
if(A[right] == target) large = right;
else if(A[left] == target) large = left;
return large - small + 1;
}
};
<code><pre>
