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

来自:程序员乔戈里(微信号:CXYqiaogeli),作者:乔戈里qgl

每天一道剑指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;
   }
}

结束语

作者乔戈里亲历2019秋招,哈工大计算机本硕,百度java工程师


推荐↓↓↓
算法与数据结构
上一篇:漫画:如何实现大整数相加? 下一篇:每天一道leetcode-最大子序和