剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程
剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
限制:
0 <= 数组长度 <= 50000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
由于有序数组中查找——二分查找
找到后左右扩展,统计相同并返回
题解
/**
* Solution
*
* @author yuzuki
* @date 2021/4/6 21:20
* @since 1.0.0
*/
public class Solution {
public int search(int[] nums, int target) {
if (nums.length == 1 && nums[0] == target){
return 1;
}
int left = 0,right = nums.length-1;
int res = 0;
// 要<= 否则出现调整后正好相等的情况也许做一次判定
while (left<=right){
int mid = (left+right)/2;
if (target<nums[mid]){
right = mid-1;
}else if (target>nums[mid]){
left = mid+1;
}else {
res++;
int now0 = mid-1;
int now1 = mid+1;
// 相等,找到 左右扩展 必须做边界限定
while (now0>=0&&nums[now0] == target){
res++;
now0--;
}
// 相等,找到 左右扩展
while (now1<nums.length&&nums[now1] == target){
res++;
now1++;
}
break;
}
}
return res;
}
public static void main(String[] args) {
// int[] a = {5,7,7,8,8,10};
// System.out.println("new Solution().search(a,8) = " + new Solution().search(a, 8));
// int[] a = {1,4};
// System.out.println("new Solution().search(a,8) = " + new Solution().search(a, 4));
int[] a = {1,1,2};
System.out.println("new Solution().search(a,8) = " + new Solution().search(a, 1));
}
}