首页 > 其他分享 >数字在排序数组中出现的次数

数字在排序数组中出现的次数

时间:2023-04-28 15:22:06浏览次数:33  
标签:下标 end nums int mid 次数 数组 return 排序

class Solution {
public:
//二分找出k第一次,最后一个k后面的下标,相减就是答案
    int getNumberOfK(vector<int>& nums , int k) {
        int n=nums.size();
        if(!n)  return 0;
        //找到第一个≥k的下标
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]<k) l=mid+1;
            else r=mid;
        }
        int start=l;
        if(nums[start]!=k)  return 0;
        //找到最后一个≤k的下标
        l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(nums[mid]>k) r=mid-1;
            else l=mid;
        }
        int end=l;
        return end-start+1;
    }
};

标签:下标,end,nums,int,mid,次数,数组,return,排序
From: https://www.cnblogs.com/tangxibomb/p/17362305.html

相关文章

  • Python很多时候要从键盘连续输入一个数组,并用空格隔开;Python爬取一些数据;python pip安
    Python要从键盘连续输入一个数组,并用空格隔开,Python中的实现方法如下:str=input(‘以空格为间隔连续输入一个数组:’)然后在键盘中输入,会·得到的str为一个字符串,要将其转为一个列表有两种方法方法一:a=[int(n)forninstr_in.split()]方法二:a=list(map(int,str.strip().sp......
  • List集合排序 sort方法
    List集合排序sort方法:publicstatic voidsort(List list):将集合中元素按照默认规则排序。publicstatic voidsort(List list,Comparator<?superT>):将集合中元素按照指定规则排序。sort方法的重载使用11.字符串作为集合中的类型进行排序publicclassDe......
  • 详解八大排序(附动图和源码)
    目录......
  • HJ93 数组分组
    修改1: 修改2: 修改3:(正确答案)  修改4:优化修改3。在修改3代码实现,尽管找到了一组可行的true,但仍然会执行后面的递归。可进行优化找到一组true后不再进行后面的递归尝试。优化实现方式是,找到一组true后,之后其他递归全部执行返回。1#no=input()2a=list(map(int,input......
  • 1005. K 次取反后最大化的数组和
    给你一个整数数组nums和一个整数k,按以下方法修改该数组:选择某个下标i并将nums[i]替换为-nums[i]。重复这个过程恰好k次。可以多次选择同一个下标i。以这种方式修改数组后,返回数组可能的最大和。输入:nums=[4,2,3],k=1输出:5解释:选择下标1,nums变为[4,......
  • 1280. 学生们参加各科测试的次数
    【题目】学生表:Students+---------------+---------+|ColumnName  |Type   |+---------------+---------+|student_id   |int    ||student_name |varchar|+---------------+---------+主键为student_id(学生ID),该表内的每一行都记录有学校一名学生的......
  • 643. 子数组最大平均数 I
    给你一个由n个元素组成的整数数组nums和一个整数k。请你找出平均数最大且长度为k的连续子数组,并输出该最大平均数。任何误差小于10-5的答案都将被视为正确答案。 示例1:输入:nums=[1,12,-5,-6,50,3],k=4输出:12.75解释:最大平均数(12-5-6+50)/4=51/4=12.7......
  • wordpress产品排序
    updatewp_postssetmenu_order=100wherepost_type='product';updatewp_postssetmenu_order=5wherepost_name='r-m-williams-craftsman-boot_792c678e';updatewp_postssetmenu_order=10wherepost_name='r-m-williams-rod-polo_ee292998......
  • c语言中,字符数组名 与 指向字符串常量的指针之间的关系
    chara[]="hello";//定义一个字符数组a,constchar*b="hello";//定义一个指向字符的指针b,指向字符串常量的第一个字符的首地址区别:a是一个指针常量,它本身的值不能修改,即char*consta;b是一个常量指针,它所指向的值不能修改,constchar*b;......
  • 【二分查找】LeetCode 153. 寻找旋转排序数组中的最小值
    题目链接153.寻找旋转排序数组中的最小值思路首先分析一下旋转数组可能有的状态:左<中<右,此时最小值肯定在左边,应当收缩右边界左<中,中>右,此时最小值肯定在右半段,应当收缩左边界左>中,中<右,此时最小值肯定在左半段,应当收缩右边界分析这三种状态可以发现,中值小......