剑指offer——56在排序数组中查找数字

题目描述

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

题解：

　　使用二分法找到数k然后向前找到第一个k，向后找到最后一个k，即可知道有几个k了

　　但一旦n个数都是k时，这个方法跟从头遍历没区别，都是O(N)的复杂度

　　可以再次利用二分法，在第一次找到k的左半部分使用二分法找到不再出现k的位置，其右半部份类似。

 class Solution01 {

 public:

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

         if (data.size() == )return ;

         int L = , R = data.size() - , M;

         while (L <= R)

         {

             M = (R - L) /  + L;

             if (data[M] == k)break;

             else if (data[M] > k)R = M - ;

             else L = M + ;

         }

         if (L > R)return ;

         L = R = M;

         int res = ;

         while (L >=  && data[L] == k) {

             res++; --L;

         }

         while (R<data.size() && data[R] == k) {

             res++; ++R;

         }

         return res - ;

     }

 };

 class Solution02 {

 public:

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

         if (data.size() == )return ;

         int pM = find(data, , data.size() - , k);

         if (data[pM] != k)return ;

         int pL = pM, pR = pM;

         while (pL !=- && data[pL] == k) pL = find(data, , pL - , k);

         while (pR != - && data[pR] == k) pR = find(data, pR + , data.size() - , k);

         return (pR == - ? data.size() : pR) - pL - ;

     }

     int find(const vector<int>data, int L, int R, const int k)

     {

         int M = -;

         while (L >=  && R < data.size() && L <= R)

         {

             M = (R - L) /  + L;

             if (data[M] == k)break;

             else if (data[M] > k)R = M - ;

             else L = M + ;

         }

         return M;

     }

 };

巴特西

剑指offer——56在排序数组中查找数字

题目描述

最新文章

热门文章