leetcode第34题

简介: 从左向右遍历,一旦出现等于 target 的值就结束,保存当前下标。如果从左到右没有找到 target,那么就直接返回 [ -1 , -1 ] 就可以了,因为从左到右没找到,那么从右到左也一定不会找到的。如果找到了,然后再从右到左遍历,一旦出现等于 target 的值就结束,保存当前下标。时间复杂度是 O(n)并不满足题意,但可以了解下这个思路,从左到右,从右到左之前也遇到过。

image.png

找到目标值的第一次出现和最后一次出现的位置,同样要求 log ( n ) 下完成。

先分享 leetcode 提供的两个解法。

解法一 线性扫描

从左向右遍历,一旦出现等于 target 的值就结束,保存当前下标。如果从左到右没有找到 target,那么就直接返回 [ -1 , -1 ] 就可以了,因为从左到右没找到,那么从右到左也一定不会找到的。如果找到了,然后再从右到左遍历,一旦出现等于 target 的值就结束,保存当前下标。

时间复杂度是 O(n)并不满足题意,但可以了解下这个思路,从左到右,从右到左之前也遇到过。

publicint[] searchRange(int[] nums, inttarget) {
int[] targetRange= {-1, -1};
// 从左到右扫描for (inti=0; i<nums.length; i++) {
if (nums[i] ==target) {
targetRange[0] =i;
break;
        }
    }
// 如果之前没找到,直接返回 [ -1 , -1 ]if (targetRange[0] ==-1) {
returntargetRange;
    }
//从右到左扫描for (intj=nums.length-1; j>=0; j--) {
if (nums[j] ==target) {
targetRange[1] =j;
break;
        }
    }
returntargetRange;
}

时间复杂度:O(n)。

空间复杂度:O(1)。

解法二 二分查找

让我们先看下正常的二分查找。

intstart=0;
intend=nums.length-1;
while (start<=end) {
intmid= (start+end) /2;
if (target==nums[mid]) {
returnmid;
    } elseif (target<nums[mid]) {
end=mid-1;
    } else {
start=mid+1;
    }
}

二分查找中,我们找到 target 就结束了,这里我们需要修改下。

我们如果找最左边等于 target 的值,找到 target 时候并不代表我们找到了我们所需要的,例如下边的情况,

image.png

此时 target == nums [ mid ] ,但由于我们改成了 end = mid - 1,所以继续更新,end 就到了 mid 的左边,此时 start > end 了,就会走出 while 循环, 我们要找的值刚好就是 start 指向的了。那么我们修改的代码如下:

while (start<=end) {
intmid= (start+end) /2;
if (target==nums[mid]) {
end=mid-1;
    } elseif (target<nums[mid]) {
end=mid-1 ;
    } else {
start=mid+1;
    }
}

找右边的同样的分析思路,就是判断需要丢弃哪一边。

所以最后的代码就出来了。leetcode 中是把找左边和找右边的合并起来了,本质是一样的。

publicint[] searchRange(int[] nums, inttarget) {
intstart=0;
intend=nums.length-1;
int[] ans= { -1, -1 };
if (nums.length==0) {
returnans;
    }
while (start<=end) {
intmid= (start+end) /2;
if (target==nums[mid]) {
end=mid-1;
        } elseif (target<nums[mid]) {
end=mid-1;
        } else {
start=mid+1;
        }
    }
//考虑 tartget 是否存在,判断我们要找的值是否等于 target 并且是否越界if (start==nums.length||nums[ start ] !=target) {
returnans;
    } else {
ans[0] =start;
    }
ans[0] =start;
start=0;
end=nums.length-1;
while (start<=end) {
intmid= (start+end) /2;
if (target==nums[mid]) {
start=mid+1;
        } elseif (target<nums[mid]) {
end=mid-1;
        } else {
start=mid+1;
        }
    }
ans[1] =end;
returnans;
}

时间复杂度:O(log(n))。

空间复杂度:O(1)。

目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
leetcode-475:供暖器
leetcode-475:供暖器
59 0
顺手牵羊(LeetCode844.)
好多同学说这是双指针法,但是我认为叫它顺手牵羊法更合适
91 0
leetcode 283 移动零
leetcode 283 移动零
65 0
leetcode第42题
也就是红色区域中的水, 数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。 原则是高度小于 2,temp ++,高度大于等于 2,ans = ans + temp,temp = 0。 temp 初始化为 0 ,ans 此时等于 2。 height [ 0 ] 等于 0 < 2,不更新。 height [ 1 ] 等于 1 < 2,不更新。 height [ 2 ] 等于 0 < 2, 不更新。 height [ 3 ] 等于 2 >= 2, 开始更新 height [ 4 ] 等于 1 < 2,temp = temp + 1 = 1。 h
118 0
leetcode第42题
leetcode第53题
解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。
leetcode第53题
leetcode第57题
和上一道可以说是一个问题,只不过这个是给一个已经合并好的列表,然后给一个新的节点依据规则加入到合并好的列表。 解法一 对应 56 题的解法一,没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题, 所以直接加过来就行了
118 0
leetcode第57题
leetcode第34题
第二种思路,参考这里。 我们开始更新 start 的时候,是 mid + 1,如果剩两个元素,例如 2 4,target = 6 的话,此时 mid = 0,start = mid + 1 = 1,我们返回 start + 1 = 2。如果 mid 是右端点,那么 mid = 1,start = mid + 1 = 2,这样就可以直接返回 start 了,不需要在返回的时候加 1 了。
122 0
leetcode第34题
leetcode第46题
这是自己开始想到的一个方法,考虑的思路是,先考虑小问题怎么解决,然后再利用小问题去解决大问题。没错,就是递归的思路。比如说, 如果只有 1 个数字 [ 1 ],那么很简单,直接返回 [ [ 1 ] ] 就 OK 了。 如果加了 1 个数字 2, [ 1 2 ] 该怎么办呢?我们只需要在上边的情况里,在 1 的空隙,也就是左边右边插入 2 就够了。变成 [ [ 2 1 ], [ 1 2 ] ]。
leetcode第46题
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
leetcode第39题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等