题目描述:
统计一个数字在排序数组中出现的次数。
提示:
•0 <= nums.length <= 105
•-109 <= nums[i] <= 109
•nums 是一个非递减数组
•-109 <= target <= 109
解题思路:排序数组中的搜索问题,首先想到 二分法 解决。
排序数组 nums 中的所有数字 target 形成一个窗口,记窗口的 左 / 右边界 索引分别为 left 和 right ,分别对应窗口左边 / 右边的首个元素。
本题要求统计数字 target 的出现次数,可转化为:使用二分法分别找到 左边界 left 和 右边界 right ,易得数字 target 的数量为 right - left - 1 。
复杂度分析:
- 时间复杂度 O(logN) : 二分法为对数级别复杂度。
- 空间复杂度 O(1) : 几个变量使用常数大小的额外空间。
class Solution{ public int search(int nums[],int target){ // 搜索右边界 right int i=0,j=nums.length-1; while(i<=j){ int m = (i+j)/2; if(nums[m]<=target) i=m+1; else j=m-1; } int right=i; // 若数组中无 target ,则提前返回 if(j>=0&&nums[j]!=target) return 0; // 搜索左边界 right i=0;j=nums.length-1; while(i<=j){ int m=(i+j)/2; if(nums[m]<target) i=m+1; else j=m-1; } int left=j; return right-left-1; } }
标签:right,target,nums,int,复杂度,Offer,53,查找,数组 From: https://www.cnblogs.com/zhz123567/p/17339456.html