作者:whisper
链接:https://www.proprogrammar.com/article/879
声明:请尊重原作者的劳动,如需转载请注明出处
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
难度:简单;标签:数组,二分查找;编程语言:C++
class Solution {
public:
//c++重写,logn复杂度
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1, mid = -1;
if(nums.size() == 0){
return 0;
}
while(right >= left){
mid = (right + left) / 2;
if(nums[mid] == target){
break;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
int left2, right2, mid2 = -1;
if(nums[mid] == target){
right2 = right;
left2 = mid;
right = mid;
while(right2 >= left2){
mid2 = (right2 + left2) / 2;
if(nums[mid2] > target){
right2 = mid2 - 1;
}else{
left2 = mid2 + 1;
}
}
while(right >= left){
mid = (right + left) / 2;
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
}else{
return 0;
}
return (nums[mid2] > target ? mid2 - 1 : mid2) - (nums[mid] < target ? mid + 1 : mid) + 1;
}
};
这里先二分查找找到一个target的位置,然后这个target位置的左右可能还有值为target的数,再左右二分查找target,最后mid, mid2就在target值的左,右边界附近了,注意return值要处理一下
class Solution {
public:
int search(vector<int>& nums, int target) {
int i=0, j=nums.size()-1;
while(i<j){
int mididx = (i+j)/2;
//printf("%d,%d,%d\n", i, j, mididx);
int midnum = nums[mididx];
if(midnum > target){
if(mididx == j){
j-=1;
continue;
}
j = mididx;
}else if(midnum < target){
if(mididx == i){
i+=1;
continue;
}
i = mididx;
}else if(nums[i] < target){
i++;
}else if(nums[j]>target){
j--;
}else{
break;
}
}
//printf("i:%d,j:%d\n", i, j);
if(j==i && nums[i]!=target)
{
return 0;
}
int ret = j-i+1;
return ret;
}
};
上面的意思是先二分找值为target的数,找到后左右指针每次+1,-1(不再二分)向找到的值target的数靠近,直到左,右(i, j)位置的数值都是target,如果中间有数不为target,再次二分,为target,再+1, -1,如此反复
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202205 | 1 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论