数组:数组在排序数组中出现的次数(!未)

原创
2020/07/02 11:32
阅读数 67

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

思路:

1.暴力法:直接循环遍历,但一般会因为限制时间过不了。
2.二分法:排序可以想到二分查找,那么

(!未)a.规定两个指针,high->第一个大于目标值的数字,low->第一个出现的目标值(不存在就指向第一个大于目标值的),high-low就是出现的次数了。

b.先找到符合条件的数字,然后一个向后一个向前找符合条件的数字,同时累加次数.

代码:

import java.util.Arrays;
public class Solution {
	//2.b
    public int GetNumberOfK(int [] array , int k) {
       int index=Arrays.binarySearch(array,k);
        if(index<0) return 0;
        int res=1;
        //向后遍历
        for(int i=index+1;i<array.length && array[i]==k;i++){
            res++;
        }
        for(int i=index-1;i>=0 && array[i]==k;i--){
            res++;
        }
        return res;
}
}
展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部
返回顶部
顶部