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

拼搏现实的明天。 2022-04-10 09:14 135阅读 0赞

## 题目描述 ##

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

AC C++ Solution:

思路:先用二分查找找到数字在数组中的位置,然后查找该位置的左右相同的元素.

class Solution {
    public:
        int searchk(vector<int> data, int lo, int hi, int k) {
            while(lo <= hi) {
                int mid = (lo+hi)/2;
                if(data[mid] == k)
                    return mid;
                else if(data[mid] < k)
                    lo = mid+1;
                else 
                    hi = mid-1;
            }
            
            return -1;
        }
        
        int GetNumberOfK(vector<int> data ,int k) {
            int len = data.size();
            if(len == 0)
                return 0;
            
            int kindex = 0;
            
            kindex = searchk(data,0,len-1,k);
            
            if(kindex == -1)
                return 0;
            
            int cnt = 1;
            int m = kindex-1;
            int n = kindex+1;
            
            while(m >= 0 && data[m] == k) {
                m--;
                cnt++;
            }
            
            while(n < len && data[n] == k) {
                n++;
                cnt++;
            }
            
            return cnt;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer - 数字在排序数组中出现的次数

include<string.h> class Solution { public: int GetNumberOfK(vector<i

太过爱你忘了你带给我的痛/ 2022年09月25日 01:29/ 0 赞/ 103 阅读

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

注意：在写代码的时候注意细节，注意细节，注意细节，重要的事情说三遍！！！ include <iostream> include <stack>

向右看齐/ 2022年08月09日 02:17/ 0 赞/ 125 阅读

相关剑指Offer | 数字在排序数组中出现的次数

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

系统管理员/ 2022年05月23日 05:52/ 0 赞/ 152 阅读

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

题目描述统计一个数字在排序数组中出现的次数。解题思路一个数字在排序数组中的分布一定是连续的，题目其实是一个在排序数组中查找数字的意思，我使用二分查找代

待我称王封你为后i/ 2022年05月21日 05:18/ 0 赞/ 146 阅读

相关【剑指Offer】37数字在排序数组中出现的次数

题目描述统计一个数字在排序数组中出现的次数。时间限制：1秒；空间限制：32768K；本题知识点：数组解题思路思路一先找循环到第一个相同数的位置索

╰+哭是因爲堅強的太久メ/ 2022年05月04日 14:56/ 0 赞/ 177 阅读

相关剑指offer:数字在排序数组中出现的次数

题目描述统计一个数字在排序数组中出现的次数。 AC C++ Solution: 思路:先用二分查找找到数字在数组中的位置,然后查找该位置的左右相同的元素.

拼搏现实的明天。/ 2022年04月10日 09:14/ 0 赞/ 136 阅读

相关剑指Offer-数字在排序数组中出现的次数

题目描述统计一个数字在排序数组中出现的次数。解题思路—二分查找：不要拿到题目就想着循环遍历数组判断大小，一定要有这个意识，题目提到有序数列，就想到二分！通过二分查找

╰+攻爆jí腚メ/ 2022年02月19日 06:15/ 0 赞/ 173 阅读

相关 [剑指offer]数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。 class Solution { public: int GetNumberOfK(vect

女爷i/ 2021年11月22日 09:16/ 0 赞/ 215 阅读

相关剑指offer--数字在排序数组中出现的次数（java）

剑指offer--数字在排序数组中出现的次数两种常见解法： 1. 遍历一遍数组，进行查找，这个方法没有利用排序数组这个条件。时间复杂度较高时间复

本是古典何须时尚/ 2021年10月26日 15:30/ 0 赞/ 224 阅读

相关 37.数字在排序数组中出现的次数——剑指offer

//因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5 //这两个数应该插入的位置，然后相减即可。 cla

╰+攻爆jí腚メ/ 2021年10月01日 05:00/ 0 赞/ 238 阅读