栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer 67. 数字在排序数组中出现的次数-java

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer 67. 数字在排序数组中出现的次数-java

acwing 67. 数字在排序数组中出现的次数

二分

原题链接

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

例如输入排序数组 [1,2,3,3,3,3,4,5] 和数字 3,由于 3 在这个数组中出现了 4 次,因此输出 4。

数据范围
数组长度 [0,1000]。

代码案例:输入:[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出:4

题解

首先是排序数组 可以用二分 如果采用双指针 或者哈希表那种的话 复杂度会多 二分的话复杂度低


就是寻找两个圆圈一减 二分的话最后l=r 那个点就是K
第一个寻找的时候 找到了 然后把left = l
第二次再用边界一减 r-left +1 或者l -left + 1也可以

class Solution {
    public int getNumberOfK(int[] nums, int k) {
        if(nums.length == 0) return 0 ;
        int l = 0 ;
        int r = nums.length - 1 ;
        while(l < r ){
            int mid = l + r >> 1;
            if(nums[mid] >= k) r = mid ;
            else  l = mid +1 ;
        }
        if(nums[r] != k) return 0 ;
         int left = l ;
         l = 0;
          r = nums.length - 1 ;
          while(l < r ){
            int  mid = l + r + 1 >> 1 ;
              if(nums[mid] <= k ) l = mid ;
              else r = mid-1;
          }
        return r - left +1 ;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981183.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号