数字在排序数组中出现的次数（Java）

本文主要是介绍数字在排序数组中出现的次数（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

统计一个数字在排序数组中出现的次数。例如输入排序数组{1， 2， 3， 3， 3， 3， 4， 5}和数字3，由于3在这个数组中出现了4次，因此输出4。

思路：

第一种解法：蛮力法，顺序遍历数组，统计出数字3出现的次数，不过这时就没有利用到题目中给的有序，故时间复杂度过大，不符合要求。

第二种解法：利用二分查找的思想（时间复杂度log(n)）来解决问题。首先先找到数组中3出现的第一个位置first3，然后再找到数组中3最后一次出现的位置end3，first3 - end3 + 1就是数字3出现的次数。

代码实现：

public class Main {//找出第一个k的位置private int getFirstK(int nums[], int k, int start, int end){if(start > end){return -1;}int middleIndex = (start + end) /2;int middleData = nums[middleIndex];if(middleData == k){//找出第一个位置k的终止条件：要么middleIndex=0;要么middleIndex > 0但是middleIndex-1处的位置不等于kif((middleIndex > 0 && nums[middleIndex-1]!=k) || middleIndex == 0){retu

这篇关于数字在排序数组中出现的次数（Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---