JZ37 数字在升序数组中出现的次数

谁借莪１个温暖的怀抱￠ 2022-09-12 04:51 92阅读 0赞

**描述:**  
给定一个长度为 n的非降序数组和一个非负数整数k，要求统计k在数组中出现的次数.  
**示例1**

输入：[1,2,3,3,3,3,4,5],3
    返回值：4

**思路:用传统的暴力破解很轻松就能做出来,这里考察主要是二分查找, 看到有序的数组进行查找,第一眼想到的就是采用二分来进行查找.**  
**1.这里我在写二分查找的时候,有几个地方需要注意:在写大循环,while(low<=high)的时候符号是<=.**  
**2.在最后通过二分查找找到目标值k之后,定义两个指针向两边进行查找完毕之后,要记得break,结束循环,经常写算法题遇到时间复杂度过高的问题就是在于一些break的使用**

public class Solution { 
        public int GetNumberOfK(int [] array , int k) { 
            int low=0;
            int high=array.length-1;
            int count=0;
            while(low<=high){ 
                int mid=low+(high-low)/2;
                if(array[mid]<k){ 
                    low=mid+1;
                }else if(array[mid]>k){ 
                    high=mid-1;
                }else{ 
                    count++;
                    int index1=mid-1;
                    int index2=mid+1;
                    while(index1>=0 && array[index1]==k){ 
                        count++;
                        index1--;
                    }
                    while(index2<array.length && array[index2]==k){ 
                        count++;
                        index2++;
                    }
                    break;
                }
            }
            return count;
        }
    }