2 solutions
-
0
题目描述:
给定一个经过旋转的升序数组,要求找到目标值
t
在数组中的开始位置和结束位置,若不存在则返回-1 -1
。输入包含三个部分:数组长度n
,长度为n
的循环数组,以及目标值t
。输出为两个整数,表示目标值的开始和结束位置的下标。思路
-
查找序列起点: 循环数组是一个有序序列的旋转版本,所以我们可以通过寻找数组中一个逆序的地方来确定这个序列的实际起点。在升序数组中,如果我们发现某个数比它前面的数要小,那么可以认为这个地方是数组的起点。
-
遍历查找目标值: 找到起点后,我们需要从起点开始遍历整个数组,同时要注意循环的特性,可以使用
(i + s) % n
来实现循环效果。这样可以在旋转后的数组中还原到原来的顺序。 -
找到目标值的开始和结束位置: 在遍历时,如果当前元素等于目标值
t
,我们更新目标值的开始位置和结束位置。第一次遇到目标值时,记录开始位置;每次遇到目标值时,都更新结束位置。 -
时间复杂度: 查找旋转点的时间复杂度是 ,遍历数组查找目标值的时间复杂度也是 ,因此总的时间复杂度是 。
代码说明:
-
查找旋转点:
- 通过遍历数组,从第二个元素开始,查找第一个小于前一个元素的地方,这就是旋转数组的实际起点。起点的索引保存在
s
中。
- 通过遍历数组,从第二个元素开始,查找第一个小于前一个元素的地方,这就是旋转数组的实际起点。起点的索引保存在
-
遍历查找目标值:
- 使用
(i + s) % n
计算经过旋转后的索引,来模拟从旋转数组起点开始遍历的效果。 - 如果找到目标值
t
,第一次匹配时设置start
,每次匹配时更新end
,这样可以得到目标值的起始位置和结束位置。
- 使用
-
输出结果:
- 最终输出
start
和end
。如果没有找到目标值,默认值-1
表示没有找到。
- 最终输出
代码
C++
java
python
-
- 1
Information
- ID
- 55
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- # Submissions
- 628
- Accepted
- 138
- Uploaded By