【剣指offer】37.ソート配列に数値が表示される回数

タイトル
ソート配列に表示される数値の回数を統計します.
ぶんせき
問題では配列が秩序配列であることを説明するため,この問題では二分ルックアップkを用いる.主な考え方は以下の通りである.

配列が空と配列に1つの要素があり、kがその要素と等しくない場合、直接0を返す.

配列に1つの要素があり、kがその要素と等しい場合、直接1を返す.

そうでなければ二分検索を有効にし、kが見つからない場合は直接0を返す.

kが配列中の位置を見つけ、それぞれ左と右にkを検索し、重複するkが含まれているかどうかを判断し、カウントする.

githubリンク:JZ 37-ソート配列に数値が表示される回数
C++コード

#include 
#include 
using namespace std;

class Solution {
	public:
	    int GetNumberOfK(vector<int> data ,int k) {
			int size = data.size();
			if(size == 0){
				return 0;
			}
			
			if(size == 1 && data[0] == k){
				return 1;
			}else if(size == 1 && data[0] != k){
				return 0;
			}
			
			//           k        
			int index = this->Find(data,k);
			
			//  index -1，         k 
			if(index == -1){
				return 0;
			}
			
			//              
			int cnt = 1;
			for(int i = index-1 ; i >= 0 ; i--){
				if(data[i] == k){
					cnt++;
				}else{
					break;
				}
			}
			//              
			for(int i = index+1 ; i < size ; i++){
				if(data[i] == k){
					cnt++;
				}else{
					break;
				}
			}
			return cnt;
	    }
	    
	    int Find(vector<int> data ,int k){
	    	int low = 0;
	    	int high = data.size() - 1;
	    	int mid;
	    	while(low <= high){
	    		mid = (low + high) / 2;
	    		if(data[mid] > k){
	    			high = mid - 1;
				}else if(data[mid] < k){
					low = mid + 1;
				}else{
					break;
				}
			}
			//   low high   ，    k      k 
			if(data[mid] != k){
				mid = -1;
			}
			return mid;
		}
};

int main()
{
	int n,k;
	while(cin>>n>>k){
		vector<int> array(n);
		for(int i = 0 ; i < n ; i++){
			cin>>array[i];
		}
		Solution s;
		cout<<s.GetNumberOfK(array,k);
	}
	
	return 0;
}