剑指offer：数字在排序数组中出现的次数

向右看齐 2022-08-09 02:17 125阅读 0赞

注意：在写代码的时候注意细节，注意细节，注意细节，重要的事情说三遍！！！

#include <iostream>
    #include <stack>
    #include <vector>
    #include <algorithm>
    #include <string>
    
    using namespace std;
    
    
    class Solution {
    public:
        int GetNumberOfK(vector<int> data ,int k) {
            int start = getFirstPos(data,k,0,data.size()-1);
    		int end = getEndPos(data,k,0,data.size()-1);
    
    		int num = 0;
    
    		if(start > -1 && end > -1)
    		{
    			num = end - start + 1;
    		}
    		return num;
        }
    
    	/* 得到第一个数字的开始位置*/
    	int getFirstPos(vector<int> data, int k ,int start ,int end)
    	{
    		if(start > end)
    			return -1;
    
    		int mid = (start + end) / 2;
    		int middata = data[mid];
    
    		
    
    		if(middata == k)
    		{
    			/* 判断是不是开头 */
    			if((mid >0 && data[mid-1] != k) || mid == 0)
    			{
    				return mid;
    			}
    			else
    			{
    				end = mid - 1;
    			}
    		}
    		else
    		{
    			if(middata > k)
    				end = mid -1;
    			else
    				start = mid + 1;
    		}
    
    		
    		return getFirstPos(data,k,start,end);
    	}
    
    	/* 得到第一个数字的结束位置*/
    	int getEndPos(vector<int> data, int k ,int start ,int end)
    	{
    		if(start > end)
    			return -1;
    
    		int mid = (start + end) / 2;
    		int middata = data[mid];
    		
    		if(middata == k)
    		{
    			/* 判断是不是结尾 */
    			if((mid < data.size() - 1  && data[mid+1] != k) || mid == data.size() - 1)
    			{
    				return mid;
    			}
    			else
    			{
    				start = mid + 1;
    			}
    		}
    		else
    		{
    			if(middata > k)
    				end = mid -1;
    			else
    				start = mid + 1;
    		}
    		
    		return getEndPos(data,k,start,end);
    	}
    
    
    };
    
    int main()
    {
    	int a[] = {1,2,3,3,3,3,4,5};
    	Solution s;
    
    	vector<int> vec(a,a+8);
    
    	cout << s.GetNumberOfK(vec,3)<< endl; 
    
    	return 0;
    }