专栏首页Java那些事每天一道剑指offer-数字在排序数组中出现的次数

每天一道剑指offer-数字在排序数组中出现的次数

每天一道剑指offer-数字在排序数组中出现的次数 https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目详述

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

题目详解

思路

  • 有序和数组这个两个字眼结合起来,肯定是要用到二分查找这一类;
  • 首先就是找最左侧的下标,利用二分查找首先是找到有一个值是与目标值target是相等的,然后因为是找最左侧的下标,所以把right=mid-1来一直往左边去逼近最左侧的值;
  • 至于找最右侧的下标就是,将left=mid+1,来去逼近最右侧的下标;
  • 如果没有找到则说明不存在返回-1;

示例

  • 这里举一个例子帮助大家理解,对于数组[1,2,4,4,4,4,4,5,6],找4的最左下标。
  • 对于这个数目来说,lfet,right,mid分别代表下标值首先left=0.right=8,所以mid=(0+8)/2 = 4;
  • 由于target=4与nums[mid]相等,所以此时记录下来这个下标,也就是mid的值4,这个下标是可能的最左的4的下标所以要记录保存一下;
  • 观察这个数组,可以知道,最左的4的下标是2,所以为了找到这个最左的下标,需要令right的值去等于mid-1;这样就把right这一边慢慢地往左靠,因为是找最左的嘛~,所以肯定是要缩小right的的值去逼近这个最左的4,直到找到这个最左的4为止~;
  • 找最右边的4的思路也是一样的哦,就是令left=mid+1去逼近最右边的这个4.

代码

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int leftIndex = -1,start=0,end=array.length-1,rightIndex=-1;
        while(start <= end)
        {
            int mid = (start+end)/2;
            if(array[mid] > k)
            {
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else{
                leftIndex = mid;
                end = mid-1;
            }
        }
        start = 0;
        end = array.length-1;
        while(start <= end)
        {
            int mid = (start+end)/2;
            if(array[mid] > k)
            {
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else{
                rightIndex = mid;
                start = mid+1;
            }
        }
        if(array.length == 0 || rightIndex == -1)
            return 0;
        return rightIndex-leftIndex+1;
    }
}

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli),作者:乔戈里qgl

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道leetcode-33

    目前准备每天刷一道题leetcode的题目,以此来激励那些零基础入门的人,千万不要被什么科班和非科班的说法吓倒了,计算机这个行业只要你肯努力,没有什么逾越不了的...

    乔戈里
  • 每天一道leetcode069-x的平方根

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。...

    乔戈里
  • 每天一道剑指offer-左旋转字符串

    ,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。 剑指offer思路,先反转整个字符串,就是fedZYXcba,然...

    乔戈里
  • 机器学习|二分法迭代求零点

    01 — 二分法求解 对于区间 [a,b] 上单调连续,且 f(a)· f(b)< 0 的函数 y = f(x),通过不断地把函数 f(x)的零点所在的区间一...

    double
  • 二分查找

    绝命生
  • LeetCode 1095. 山脉数组中查找目标值(二分查找)

    给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

    Michael阿明
  • leetcode: 69. Sqrt(x)

    JNingWei
  • 基于FPGA的中值滤波算法的实现

    中值滤波法是一种非线性平滑技术,它将每一像素点的灰度值设置为该点某邻域窗口内的所有像素点灰度值的中值.

    FPGA开源工作室
  • LeetCode 图解 | 540. 有序数组中的单一元素

    题目来源于 LeetCode 上第 540 号问题:有序数组中的单一元素。题目难度为中等,目前通过率60.2%。

    五分钟学算法
  • 二分查找模版

    二分:精确查找 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #inclu...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券