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

女爷i 2021-11-22 09:16 217阅读 0赞

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

class Solution {
    public:
        int GetNumberOfK(vector<int> v ,int k) {
            int len=v.size(),c=0;
            if(len==0)return 0;
            int first=binarySearchFirst(v,k,0,len-1);
            int last=binarySearchLast(v,k,0,len-1);
            if(first!=-1 && last!=-1)
            	return last-first+1;
            else
                return 0;
        }
        int binarySearchFirst(vector<int>&v,int k,int l,int r){
            if(l>r)return -1;
            //bool flag=v[l]<=v[r]?1:0;
            
            int mid=l+(r-l)/2;
            
            if(v[mid]==k){
                if(l==mid || v[mid-1]!=k)
                    return mid;
                else
                    r=mid-1;
            }
            else{
                if(v[mid]>k)
                    r=mid-1;
                else
                    l=mid+1;
            }
            
            return binarySearchFirst(v,k,l,r);
        }
        
        int binarySearchLast(vector<int>&v,int k,int l,int r){
            if(l>r)return -1;
            //bool flag=v[l]<=v[r]?1:0;
            
            int mid=l+(r-l)/2;
            
            if(v[mid]==k){
                if(r==mid || v[mid+1]!=k)
                    return mid;
                else
                    l=mid+1;
            }
            else{
                if(v[mid]>k)
                    r=mid-1;
                else
                    l=mid+1;
            }
            
            return binarySearchLast(v,k,l,r);
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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