題目描寫敘述
統計一個數字在排序數組中出現的次數。
解題思路
數組是排序的，所以反復出現的數字是相鄰排列的。
用二分查找算法，找到第一次出現的位置。和 最后一次出現的位置。
推斷第一次出現的位置條件為：當前數字的前一個是否與之相等。若是則繼續查找，否則該位置就是第一次出現的位置。
推斷最后一次出現的位置條件為：當前數字的后一個是否與之相等，若是則繼續查找，否則該位置就是最后一次出現的位置。
出現的次數= last - first +1
時間復雜度：O(logn)
實現代碼
class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {int result=0;if(data.empty())return 0;int start = 0;int end = data.size()-1;int first = getFirstK(data,k,start,end);int last = getLastK(data,k,start,end);if(first >-1 && last >-1)result = last - first+1;return result;}int getFirstK(vector<int> data, int k, int start, int end){if(start > end)return -1;int midIndex = (start + end)/2;int midData = data[midIndex];if(midData == k){if(midIndex > 0 && data[midIndex-1] != k || midIndex == 0)return midIndex;elseend = midIndex-1;}else if(midData > k)end = midIndex-1;elsestart = midIndex+1;return getFirstK(data,k,start,end);}int getLastK(vector<int> data, int k, int start, int end){if(start > end)return -1;int midIndex = (start + end)/2;int midData = data[midIndex];if(midData == k){if(midIndex < data.size()-1 && data[midIndex+1] != k || midIndex == data.size()-1)return midIndex;elsestart = midIndex+1;}else if(midData > k)end = midIndex-1;elsestart = midIndex+1;return getLastK(data,k,start,end);}
};
)
