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

题目

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

思路

既然是已经排序好的数组&＃xff0c;那么第一个想到的就是二分查找法。

做法就是使用二分法找到数字在数组中出现的第一个位置&＃xff0c;再利用二分法找到数字在数组中出现的第二个位置。时间复杂度为O(logn &＃43; logn)&＃xff0c;最终的时间复杂度为O(logn)。

举个例子&＃xff0c;找到数字k在数组data中出现的次数。

数组data中&＃xff0c;数字k出现的第一个位置&＃xff1a;

我们对数组data进行二分&＃xff0c;如果数组中间的数字小于k&＃xff0c;说明k应该出现在中间位置的右边&＃xff1b;如果数组中间的数字大于k&＃xff0c;说明k应该出现在中间位置的左边&＃xff1b;如果数组中间的数字等于k&＃xff0c;并且中间位置的前一个数字不等于k&＃xff0c;说明这个中间数字就是数字k出现的第一个位置。

同理&＃xff0c;数字k出现的最后一个位置&＃xff0c;也是这样找的。但是判断少有不同。我们使用两个函数分别获得他们。

代码

public class Solution {/*** 博客上的解题思路&＃xff0c;也就是剑指offer的思路* 首先用递归二分法找到第一个k和最后一个k&＃xff0c;然后得到个数* &＃64;param array* &＃64;param k* &＃64;return*/public int GetNumberOfK(int [] array , int k) {int num &＃61; 0;if (array !&＃61; null && array.length >0) {int firstk &＃61; getFirstK(array, k,0, array.length-1);int lastk &＃61; getLastK(array, k,0, array.length-1);if (firstk > -1 && lastk > -1) num &＃61; lastk -firstk &＃43;1;}return num;}/** 找到第一个出现的数字的下标*/public int getFirstK(int [] array, int k,int start, int end) {if(start > end)return -1;int midindex &＃61; (start &＃43; end)/2;int middata &＃61; array[midindex];if (middata &＃61;&＃61; k) {//判断是不是第一个K&＃xff0c;前一个不等于K&＃xff0c;就是第一个Kif(midindex > 0 && array[midindex - 1]!&＃61;k||midindex &＃61;&＃61; 0)return midindex;elseend &＃61; midindex -1;//如果不是第一个k&＃xff0c;那么肯定是在前面找&＃xff0c;所以end要往前放}else if (middata > k) {end &＃61; midindex -1; //二分&＃xff0c;如果这个大于k&＃xff0c;所以要在前面找}elsestart &＃61; midindex &＃43; 1;// 如果小于k&＃xff0c;说明要往后找return getFirstK(array,k, start, end);}/** 找到最后一个出现的数字的下标*/public int getLastK(int [] array, int k,int start, int end) {if(start > end)return -1;int midindex &＃61; (start &＃43; end)/2;int middata &＃61; array[midindex];if(middata &＃61;&＃61; k) {//判断是不是最后一个K&＃xff0c;后一个不等于K&＃xff0c;就是最后一个Kif(midindex k) {end &＃61; midindex - 1;}else start &＃61; midindex &＃43;1;return getLastK(array, k,start, end);}
}

LeetCode

class Solution {public int[] searchRange(int[] nums, int target) {int[] relist &＃61; new int[2];// if(nums.length <&＃61;0 ||nums &＃61;&＃61; null){// return relist;// }//求第一个relist[0] &＃61; GetFirst(nums,nums.length,target,0,nums.length-1);relist[1] &＃61; GetLast(nums,nums.length,target,0,nums.length-1);//求最后一个return relist;}private static int GetFirst(int[] nums, int length, int target, int start, int end) {if(start > end){return -1;}int middle &＃61; (start&＃43;end)/2;if(nums[middle] > target){//说明开始值在左边end &＃61; middle-1;}else if(nums[middle] 0 && nums[middle-1] !&＃61; target) || middle &＃61;&＃61;0){return middle;}else {end &＃61; middle-1;}}return GetFirst(nums,length,target,start,end);}private static int GetLast(int[] nums, int length, int target, int start, int end) {if(start > end){return -1;}int middle &＃61; (start&＃43;end)/2;if(nums[middle] target){//说明结束值在左边end &＃61; middle-1;}else {//说明开始值可能就在中间if((middle }