剑指 重复数字个数

可以通过循环O(n)，二分O(logn) 二分可以直接递归，也可以直接找左右边界，做差。

# -*- coding:utf-8 -*-
class Solution:
#     def __init__(self):
#         self.count=0
    def GetNumberOfK(self, data, k):
        # write code here
#         count=0
#         for i in range(len(data)):
#             if data[i]==k:
#                 while  i<len(data) and data[i]==k:
#                     count+=1
#                     i+=1
#                 return count
#         return count

#         def binary_search(left,right):


#             if left>right:return 

#             mid=(right-left)//2+left
#             if data[mid]<k:
#                 binary_search(mid+1, right)
#             elif data[mid]>k:
#                 binary_search(left, mid-1)
#             elif data[mid]==k:
#                 self.count+=1
#                 binary_search(left, mid-1)
#                 binary_search(mid+1, right)

#         binary_search(0, len(data)-1)
#         return self.count 
#         if len(data)==0:
#             return 0
        left=0
        right=len(data)-1
        while left<=right:
            mid=(right-left)//2+left
            if data[mid]<k:
                left=mid+1
            elif data[mid]>k:
                right=mid-1
            elif data[mid]==k:
                right=mid-1
        left_bound=left 
        #if data[left_bound]!=k:return 0

        left=0
        right=len(data)-1
        while left<=right:
            mid=(right-left)//2+left
            if data[mid]<k:
                left=mid+1
            elif data[mid]>k:
                right=mid-1
            elif data[mid]==k:
                left=mid+1

        right_bound=left

        return right_bound-left_bound

通过二分递归求解重复个数，把函数当作求一定区域内重复数字个数的函数，这样每次函数返回 count,把count也作为参数传入，函数返回值需要赋值给count,在mid值等于k时，我们需要让count+=1，然后继续在左边界和右边界寻找，因为count作为参数在函数里，动态增加，所以不用再赋值的时候count+=函数返回值，因为当前值已经是在之前的count基础上增加的了。

        def binary_search(left,right,count):


            if left>right:return count

            mid=(right-left)//2+left
            if data[mid]<k:
               count= binary_search(mid+1, right,count)
            elif data[mid]>k:
                count=binary_search(left, mid-1,count)
            elif data[mid]==k:
                count+=1
                count=binary_search(left, mid-1,count)
                count= binary_search(mid+1, right,count)
            return count

        if len(data)==0:
            return 0
        return binary_search(0, len(data)-1,0)