34. 在排序数组中查找元素的第一个和最后一个位置
程序员文章站
2022-07-08 15:58:27
...
1.题目
2.解法
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = 0;
int end = nums.length-1;
int result[] = {-1,-1};
if(nums.length==0) return result;
int count = 0;
while(start <= end) {
int mid = start + (end-start)/2;
if(nums[mid] == target) {
// 先判断左边
int tmp = mid;
// 直到最左边
while (tmp > 0 && nums[--tmp] == target) {}
if (tmp == 0 && nums[tmp] == target) {
result[count++] = tmp;
} else {
result[count++] = tmp + 1;
}
// 再判断右边
tmp = mid;
while (tmp < nums.length - 1 && nums[++tmp] == target) {
}
if (tmp == nums.length - 1 && nums[tmp] == target) {
result[count] = tmp;
} else {
result[count] = tmp -1;
}
break;
}else if(nums[mid]< target){
start = mid + 1;
}else{
end = mid-1;
}
}
return result;
}
}
时间复杂度为O(logn), 如果一个数字重复的次数很多的话,那么时间复杂度会变为O(n), 空间复杂度为O(1)
3.思考(可忽略)
这道题看看题解,很好~~
- 我忽略的最重要的一点是:
@nums[i]==target时,左右两边都得判断,是否还有target
我写的这个条件只满足,数组中只有两个重复数,并且mid-1、mid不在临界的情况
如果改为这样,条件满足了,但是执行语句不满足了,所以,只有左右两边同时判断才对,不能只走一条道
2、如果start = 0 , end = length的时候,条件为start < end, 因为前一个mid刚判断过。
3、临界条件一定要判断。
上一篇: 淘宝运营 淘宝选关键词的六种方法
下一篇: 四数相加(java数据算法)
推荐阅读
-
C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)
-
在排序数组中查找元素的第一个和最后一个位置、变形二分法
-
#leetcode刷题之路34-在排序数组中查找元素的第一个和最后一个位置
-
34. 在排序数组中查找元素的第一个和最后一个位置
-
Leetcode No.34 在排序数组中查找元素的第一个和最后一个位置
-
在排序数组中查找元素的第一个和最后一个位置(二分、lower_bound、upper_bound)
-
在排序数组中查找元素的第一个和最后一个位置
-
php中删除数组的第一个元素和最后一个元素的函数,php数组
-
php中删除数组的第一个元素和最后一个元素的函数
-
34. 在排序数组中查找元素的第一个和最后一个位置【二分待完成】