数字在升序数组中出现的次数

二分查找，参考剑指Offer,但是用的非递归。

public class Solution {
    	public  int GetNumberOfK(int[] array,int k){
		if(array==null||array.length==0)
			return 0;
		int first=getFirstK(array,k,0,array.length-1);
		int last=getLastK(array,k,0,array.length-1);
		if(first==-1 ||last==-1){
			return 0;
		}
		else{
			return last-first+1;
		}
		
	}
	
	public  int getFirstK(int[] array,int k,int start,int end){
		while(start<=end){
			int mid=(start+end)/2;
			if(k<array[mid])
				end=mid-1;
			else if(k>array[mid])
				start=mid+1;
			else{
				if((mid>0&&array[mid-1]!=k)||mid==0)
					return mid;
				else{
					end=mid-1;
				}
			}
		}
		return -1;
	}
	
	public  int getLastK(int[] array,int k ,int start,int end){
		while(start<=end){
			int mid=(start+end)/2;
			if(k<array[mid])
				end=mid-1;
			else if(k>array[mid])
				start=mid+1;
			else{
				if((mid<array.length-1&&array[mid+1]!=k)||mid==array.length-1)
					return mid;
				else{
					start=mid+1;
				}
			}
		}
		return -1;
	}
}

/*二分查找，分治递归
*/
public class Solution {
    public  int GetNumberOfK(int [] array , int k) {
    	int length = array.length;
    	if(length <=0 || array == null){
    		return 0;
    	}
    	int num = array[length/2];
    	int[] arrayLeft;
    	int[] arrayRight;
    	int count = 0;
    	if(num > k){
    		arrayLeft = Arrays.copyOfRange(array, 0, length/2);
    		count = GetNumberOfK(arrayLeft, k);
    	}
    	if(num < k){
    		arrayRight = Arrays.copyOfRange(array, length/2+1, length);
    		count = GetNumberOfK(arrayRight, k);
    	}
    	if(num == k){
    		count++;
    		int leftCount = 0;
    		int rightCount = 0;
    		int leftNum;
    		int rightNum;
    		for(int i = 1; i <= length/2; i++){
    			leftNum = array[length/2-i];
    			if(leftNum==k){
    				leftCount++;
    			}else{ 				
    				break;
    			}
    		}
    		count += leftCount;
    		for(int i = 1; i <= length/2-1;i++){
    			rightNum = array[length/2+i];
    			if(rightNum==k){
    				rightCount++;
    			}else{
    				break;				
    			}
    		}
			count += rightCount;
    	}
    	return count;
    }
}

class Solution {
private:
    int binaryFind(vector<int> &data, int begin, int end ,int k){
		int ind = -1;
		if(begin >= end) return -1;
		int mid = (end + begin) / 2;
		if(k == data[mid]) return mid;
		if((ind = binaryFind(data,begin,mid,k)) != -1) return ind;
		if((ind = binaryFind(data,mid+1,end,k)) != -1) return ind;
		return -1;
    }
    
public:
    int GetNumberOfK(vector<int> data ,int k) {
			int ind = binaryFind(data,0,data.size(),k);
			if(ind == -1) return 0;
			int pos = ind;
			int cnt = 1;
			while(--pos >= 0 && k == data[pos]) ++cnt;
			while(++ind < data.size() && k == data[ind]) ++cnt;
			return cnt;
    }
    
    
};

该题如果用python来解的话方法可以使用python提供的函数直接求得
也可以避开库函数，使用自己的方法来解
class Solution:
    # 二分法找到k值的位置
    def BinarySearch(self, data, mlen, k):
        start = 0
        end = mlen - 1
        while start <= end:
            mid = (start + end) / 2
            if data[mid] < k:
                start = mid + 1
            elif data[mid] > k:
                end = mid - 1
            else:
                return mid
        return -1

    def GetNumberOfK(self, data, k):
        # write code here
        mlen = len(data)
        # 先使用二分法找到k值的位置
        index = self.BinarySearch(data, mlen, k)
        if index == -1:
            return 0
        # 分别向该位置的左右找
        count = 1
        for i in range(1,mlen):
            if index + i < mlen and data[index+i] == k:
                count += 1
            if index - i >= 0 and data[index-i] == k:
                count += 1
        return count

int GetNumberOfK(vector<int>& A, int target) {
    if (A.empty()) return 0;

    auto it_lb = std::lower_bound(A.begin(), A.end(), target);
    auto it_ub = std::upper_bound(A.begin(), A.end(), target);

    return (it_ub - it_lb);
}

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array.length==0) return 0;
        int low = 0;
        int high = array.length-1;
        int mid = (low+high)/2;
        int count = 0;
        while(low<=high){
            mid = (low+high)/2;
            if(array[mid]>k){
                high = mid-1;
            }else if(array[mid]<k){
                low = mid+1;
            }else{    
                count = 1;
                int temp = mid-1;
                while(temp>=0 && array[temp]==array[mid]){
                    count++;
                    temp--;
                }
                temp = mid+1;
                while(temp<array.length && array[temp]==array[mid]){
                    count++;
                    temp++;
                }
                break;
            }
        }
        return count;
    }
}

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto left = lower_bound(data.begin(), data.end(), k);
        auto right = upper_bound(data.begin(), data.end(), k);
        return right - left;
    }
};

/* 先用二分查找找出某个k出现的位置，然后再分别向前和向后查找总的个数*/
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int i = binaryFind(data,0,data.size(),k);
        if( i == -1) return 0;
        int sum = 1;
        for(int j = i - 1; j >= 0; j--){
            if(data[j] == k) sum++;
            else break;
        }
        for(int j = i + 1; j < data.size(); j++){
            if(data[j] == k) sum++;
            else break;
        }
        return sum;
    }
    
    int binaryFind(vector<int> &data, int begin, int end ,int k){
        if(begin >= end) return -1;
        int mid = (begin + end) / 2;
        if(data[mid] == k) return mid;
        int res = -1;
        if((res = binaryFind(data,begin,mid,k)) != -1) return res;
        if((res = binaryFind(data,mid + 1, end,k) != -1)) return res;
        return -1;
    }
};

//因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5
//这两个数应该插入的位置，然后相减即可。
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
    }
private:
    int biSearch(const vector<int> & data, double num){
        int s = 0, e = data.size()-1;      
        while(s <= e){
            int mid = (e - s)/2 + s;
            if(data[mid] < num)
                s = mid + 1;
            else if(data[mid] > num)
                e = mid - 1;
        }
        return s;
    }
};

public int GetNumberOfK(int[] array , int k) {
    if(array == null || array.length == 0) return 0;
    int l = 0, r = array.length-1;
    int count = 0;
    while(l <= r){
        int mid = (l+r) >> 1;
        if(array[mid] < k){
            l = mid + 1;
        }else if(array[mid] > k){
            r = mid - 1;
        }else{
            count++;
            l = mid-1;
            r = mid+1;
            while(l >= 0 && array[l] == k){
                count++;
                l--;
            }
            while(r < array.length && array[r] == k){
                count++;
                r++;
            }
            break;
        }
    }
    return count;
}

# -*- coding:utf-8 -*-
# 时间复杂度O(logn),我的方法不用找最前和最后的k，是递归中直接计算k的个数
class Solution:
    def GetNumberOfK(self, data, k):
        if not data:
            return 0
        return self.helper(data,k)

    def helper(self,data,k):
        if not data:
            return 0
        left, right = 0, len(data) - 1
        mid = (left + right) // 2
        if data[mid] > k:
            return self.helper(data[:mid], k)
        elif data[mid] < k:
            return self.helper(data[mid + 1:], k)
        else:
            return 1 + self.helper(data[:mid], k) + self.helper(data[mid + 1:], k)

	

思路

• 扫描数组思路很简单，时间复杂度为O(N)，这里采用二分搜索获得logn的时间复杂度。
• 由于数组已经有序，因此只需找到开头的k和结尾的k即可。

伪代码1：找到开头的k

1. 一旦发现start>end，就说明数组中根本没有K，所以返回-1表示出错；
2. 计算中点位置，将中点的值和k进行比较： 2.1. 若k小于中点值，则在前半段找 2.2. 若k大于中点值，则在后半段找 2.3. 若k等于中点值：

    a）若中点已经是数组第一个元素，则直接返回中点位置；
    b）若中点值的前一个元素和中点值不同，则直接返回中点位置；
    c）若中点值前一个元素和中点值相同，则继续在前半段找；
   

3. 计算出新的start、end后继续递归。

伪代码2：主函数

1. 健壮性判断：若数组为空、数组的第一个元素大于k、最后一个元素小于k，则根本不存在k，直接返回0.
2. 分别计算k开头位置、结尾位置
3. 只要其中一个为-1则返回-1；否则返回（结尾-开头+1）

public int GetNumberOfK(int [] array , int k) {

    // 若序列最小值大于k、最大值小于k，则k不存在！
    if ( array==null || array.length<=0 || k < array[0] || k > array[array.length-1] ) return 0;

    int firstK = GetFirstK( array, 0, array.length-1, k );
    int lastK = GetLastK( array, 0, array.length-1, k );

    if ( firstK==-1 || lastK==-1 ) return -1;

    return (lastK-firstK)+1;
}

private int GetFirstK( int[] array, int start, int end, int k ) {
    if ( start > end ) return -1; 

    int mid = ( start+end ) >> 1;
    if ( k < array[mid] ){
        end = mid-1;
    }
    else if ( k > array[mid] ){
        start = mid + 1;
    }
    else {
        if ( mid==0 || array[mid-1]!=array[mid] ) {
            return mid;
        }
        else {
            end = mid-1;
        }
    }

    return GetFirstK( array, start, end, k );
}

private int GetLastK( int[] array, int start, int end, int k ) {
    if ( start > end ) return -1; 

    int mid = ( start+end ) >> 1;
    if ( k < array[mid] ){
        end = mid-1;
    }
    else if ( k > array[mid] ){
        start = mid + 1;
    }
    else {
        if ( mid==array.length-1 || array[mid+1]!=array[mid] ) {
            return mid;
        }
        else {
            end = mid+1;
        }
    }

    return GetLastK( array, start, end, k );
}

 //使用STL算法count 循序查找O(n)
    int GetNumberOfK(vector<int> data, int k) {
        return count(data.begin(), data.end(), k);
    }

 //利用STL的multimap容器底层以红黑树为基础,构造成本O(n),查询成本O(log n)
    int GetNumberOfK(vector<int> data, int k) {
        multiset<int> msData(data.begin(), data.end());
        return msData.count(k);
    }

    //利用STL库函数lower_bound()和upperBound(),O(log n)
    int GetNumberOfK(vector<int> data ,int k) {
        auto iter1 = lower_bound(data.begin(), data.end(), k);
        auto iter2 = upper_bound(data.begin(), data.end(), k);
        return static_cast<int>(iter2 - iter1);
    }

public int GetNumberOfK(int[] array, int k) {
        int l, r, m, l1, r1;
        for (l = 0, r = array.length - 1, m = (l + r) >> 1; l < m; m = (l + r) >> 1)
            if (k <= array[m])
                r = m;
            else
                l = m + 1;
        for (l1 = 0, r1 = array.length - 1, m = (l1 + r1) >> 1; l1 < m; m = (l1 + r1) >> 1) 
            if (k < array[m])
                r1 = m - 1;
            else
                l1 = m;

        return r > -1 && array[l] == k ? r1 - l + 1 : 0;
    }

public int GetNumberOfK(int[] array, int k) {
		if (array == null || array.length == 0)
			return 0;
		
		int t = getFirst(array, 0, array.length - 1, k);
		if (t != -1)
			return getLast(array, 0, array.length - 1, k) - t + 1;
		
		return 0;
	}

	int getFirst(int[] array, int s, int e, int k) {
		if (s >= e)
			return array[s] == k ? s : -1;
		
		int m = (s + e) / 2;
		if (array[m] < k)
			return getFirst(array, m + 1, e, k);
		else
			return getFirst(array, s, m, k);
	}

	int getLast(int[] array, int s, int e, int k) {
		if (s >= e) {
			if (array[s] == k)
				return s;
			return array[s - 1] == k ? s - 1 : -1;
		}
		
		int m = (s + e) / 2;
		if (array[m] <= k)
			return getLast(array, m + 1, e, k);
		else
			return getLast(array, s, m, k);
	}

class Solution:
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        return data.count(k)

    
//这题就用二分先找到一个，再判断前面和后面的数是不是也为目标值就行了
int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()==0)
            return 0;
        int l =0,n=data.size()-1;
        while(l<=n)
        {
            int mid = (l+n)/2;
            if(data[mid]==k)
            {
                int count =0;
                int m=mid;
                while(mid>=0&&data[mid]==k)//判断前一个是否为目标值（注意防止数组越界）                  {
                    count+=1;
                    mid--;
                }
                
                while(m+1<=n&&data[m+1]==k)//判断后一个是否为目标值（注意防止数组越界）
                {
                    count++;
                    m++;
                }
                return count;
            }
            if(data[mid]>k)
            {
                n=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return 0;
    }

int find(int*data,int len,int k,int flag)
{
    int left=0,right=len-1,mid;
    while(left<=right){
        mid=left+(right-left)/2;
        if(data[mid]>k)
            right=mid-1;
        else if(data[mid]<k)
            left=mid+1;
        else{
            if(flag==0){//flag==0，找最左边数字，
                if(mid==left ||data[mid-1]!=k) return mid;
                else right=mid-1;//把中心向左推
            }else {
                if(mid==right||data[mid+1]!=k) return mid;
         else left=mid+1;
            }
        }
    }
    return -1;
}

int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    if(dataLen==0) return 0;
    int left=find(data,dataLen,k,0);
    int right=find(data,dataLen,k,1);
    if(left==-1&&right==-1) return 0;//没找到
    return right-left+1;
}

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        // 二分法：
//         return binary1(array,k+1)-binary1(array,k);
        return binary2(array,k+1)-binary2(array,k);
    }
    
    // 二分查找模板1
    public int binary1(int [] array , int k){
        
        int left = 0;
        // 如果区间定义的是左闭右闭
        int right = array.length-1;
        // while里必须用等号
        while(left<=right){
            // 这么写可以防溢出？
            int mid = left + ((right-left)>>1);
            // 这里的=是由题目而定的，本题中我们想求左边界，所以在=的情况下也左移right
            if(array[mid]>=k){
                // right这里必须-1
                right = mid -1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    // 二分查找模板2
    public int binary2(int [] array , int k){
        
        int left = 0;
        // 如果区间定义的是左闭右开
        int right = array.length;
        // while里不可以用等号
        while(left<right){
            // 这么写可以防溢出？
            int mid = left + ((right-left)>>1);
            // 这里的=是由题目而定的，本题中我们想求左边界，所以在=的情况下也左移right
            if(array[mid]>=k){
                // right 这里不可-1
                right = mid ;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}