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

题目描述：

统计一个数字在排序数组中出现的次数。

思路分析：

1. 直观思路是直接遍历一遍，统计。复杂度也只要O(n)。

2. 显然这道题要考察的内容不这么简单，实际上考虑二分的思想来完成。分别二分查找第一个k和最后一个k。具体来说，利用二分查找思想，找到k，再判断当前的前一个是否为k或是否为第一个元素，若是，则返回；否则即第一个k在前面，则右边界r左移，继续递归查找。对于最后一个k的查找思路类似。

代码：

思路二：

 class Solution {

 public:

     int GetFirstK(vector<int>data, int k, int l, int r)

     {

         if(l>r)

             return -;

         int mid = (l+r)/;

         if(data[mid]>k)

         {

             r = mid-;

         }

         else if(data[mid]<k)

         {

             l = mid+;

         }

         else

         {

             if((mid> && data[mid-]!=k) || mid==)

                 return mid;

             else

                 r = mid-;

         }

         return GetFirstK(data, k, l, r);

     }

     int GetLastK(vector<int>data, int k, int l, int r)

     {

         if(l>r)  //递归出口

             return -;

         int mid = (l+r)/;

         if(data[mid]>k)

         {

             r = mid - ;

         }

         else if(data[mid]<k)

         {

             l = mid + ;

         }

         else

         {

             if((mid<data.size()-&&data[mid+]!=k) || mid == data.size()- )

                 return mid;

             else

                 l = mid+;

         }

         return GetLastK(data, k, l, r);

     }

     int GetNumberOfK(vector<int> data ,int k) {

         if(data.size()<=)

             return ;

         int first = GetFirstK(data, k, , data.size()-);

         int last = GetLastK(data, k, , data.size()-);

         if(first==- && last ==-)

             return ;

         else

             return last-first+;

     }

 };

巴特西

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

最新文章

热门文章