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

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

http://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2

题目:统计一个数字在排序数组中出现的次数;
参数:1.传入的有序数组;2.查找的数字
思路:看到很多人采用二分查找的方法;自己写了一个类似于双指针的方法。
①:准备两个指针,遍历数组,查找是否有与指定数字相等的元素;
②:如果存在,则小指针记录下第一个等于k的索引值;
③:大指针继续向下移动,寻找小指针之后第一个与k不相等的元素索引,记录下索引值,如果一相等的话;则大指针为数组的长度值;
④返回的是大指针减去小指针的值;

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null){
            return 0;
        }
        int smallPoint=0;
        int bigPoint=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==k){
                smallPoint=i;
                break;
            }
        }
        for(int i=smallPoint;i<array.length;i++){
            if(array[i]!=k){
                bigPoint=i;
                break;
            }else{
                 bigPoint=array.length;
            }
        }
        return bigPoint-smallPoint;
    }
}
全部评论
如果数组是{1,2,3,4,4,4,4,4}第二个for循环从小指针开始从前往后遍历是不是时间复杂度就是o(N),如果改成从后往前移动,是不是就不需要遍历整个数组了呢?
点赞 回复 分享
发布于 2021-07-30 11:49
思路清晰,代码比二分法简单多了
点赞 回复 分享
发布于 2020-06-29 23:26

相关推荐

点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务