欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

某数字在排序数组中出现的次数

程序员文章站 2024-03-20 17:45:10
...

二分查找


剑指offer 上给出的解法:两个递归(循环也可以),找左边界和右边界。
但貌似时间消耗没有 先二分查找到 k ,再左右顺序遍历 少。没想清楚原因。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.size()==0 )return 0;
        if (data.size()==1)
        {
        	if (k!=data[0])return 0;
        	else return 1;
		}
		
        int ans = 0;
        
        int left = GetFirstK(data,k,0,data.size()-1);
        int right = GetLastK(data,k,0,data.size()-1);
//        cout<<left<<" "<<right<<" "<<endl;
        if (left>-1 && right>-1)
        {
        	ans = right - left +1;
            return ans;
		}
		
		else return 0;
        
        
	}
	
	int GetFirstK(vector<int>data,int k,int left,int right)
	{
		
		if (right<left)return -1;
		
		int mid = (left+right)/2;
		if (data[mid]<k)left = mid+1;
		else if (data[mid]>k)right = mid-1;
		else if (data[mid]==k)
		{
			if (mid==0 ||(mid>0 && data[mid-1]!=k))return mid;
			else
				right = mid-1;
		}
		
		return GetFirstK(data,k,left,right);
	}
	
	int GetLastK(vector<int>data,int k,int left,int right)
	{
		if (right<left)return -1;
		
		int l = data.size()-1;
		
		int mid = (left+right)/2;
		if (data[mid]<k)left = mid+1;
		else if (data[mid]>k)right = mid-1;
		else if  (data[mid]==k)
		{
			if (mid==l || (mid<l && data[mid+1]!=k))return mid;
			else left = mid+1;
		}
		return  GetLastK(data,k, left, right);
	}
	
};
-------------------------
https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2

    //循环写法
    private int getLastK(int [] array , int k, int start, int end){
        int length = array.length;
        int mid = (start + end) >> 1;
        while(start <= end){
            if(array[mid] > k){
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else if(mid+1 < length && array[mid+1] == k){
                start = mid+1;
            }else{
                return mid;
            }
            mid = (start + end) >> 1;
        }
        return -1;
    }

某大神利用 stl 的 :

https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto resultPair = equal_range(data.begin(), data.end(),k);
        return resultPair.second - resultPair.first;
    }
};