搜索旋转排序数组II
2024-10-19 01:32:44
题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [,,,,,,] 可能变为 [,,,,,,] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [,,,,,,], target =
输出: true
示例 2:
输入: nums = [,,,,,,], target =
输出: false
进阶:
- 这是https://www.cnblogs.com/guohai-stronger/p/12056691.html的延伸题目，本题中的
nums可能包含重复元素。 - 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
思想
本题是需要使用二分查找，怎么分是关键，举个例子：
- 第一类
10111 和 11101这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
- 第二类
2345671这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找
- 第三类
6712345这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。
代码
func search(_ nums: [Int], _ target: Int) -> Bool {
if nums.count <= {
return false
}
var start =
var end = nums.count -
var mid: Int =
while start <= end {
mid = start + (end - start)/
if nums[mid] == target {
return true
}
if nums[start] == nums[mid] {
start +=
continue
}
if nums[start] <= nums[mid] {
if nums[mid] > target && nums[start] <= target {
end = mid -
} else {
start = mid +
}
} else {
if nums[mid] < target && nums[end] >= target {
start = mid +
} else {
end = mid -
}
}
}
return false
}
最新文章
- 抛弃jQuery：DOM API之操作元素
- Vue.js实现checkbox的全选和反选
- 在hive中遇到的错误
- FORM中需要反复选择LOV
- 【wikioi】1116 四色问题
- jQuery基本选择器
- 离线网页制作器（beta1.0）
- python文件操作--字符串替换
- eclipse删除已经记录的用户名和密码
- HDFS 整体把握
- Java学习日记-5 关键字static和final 以及接口
- 用C#实现的条形码和二维码编码解码器
- HTTP POST和GET的区别[转]
- spring在扫描包中的注解类时出现Failed to read candidate component错误
- 小程序代码包压缩 策略&方案
- sqlmap完成简单的sql注入
- python基础四-文件读取
- pxe+Kickstart自动装机补充知识点
- linux 查看信息－进程&用户&服务&程序
- Python-CSS入门