分享
leetcode 搜索旋转排序数组 golang
lucasgao · · 740 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
81. 搜索旋转排序数组 II
解题思路
二分的变形,我们之前二分查找基于这样的一个假设:我们定位到一个元素后,这个元素的前后分别都是单调的。
但是这边的数组是旋转的。
所以我们需要修改的是判定逻辑
- 如果我们可以判定出来 那边是旋转的,那边是自增的。则可以通过边界判断
- 如果不行,则进行递归。
代码实现
func search(nums []int, target int) bool {
i,j := 0,len(nums)-1
A := nums
for i<=j{
mid := (i+j)/2
if A[mid]==target{
return true
}
if (A[mid]==A[j]||A[mid]==A[i]) && (search(nums[mid+1:j+1],target) || search(nums[i:mid],target)){
return true
}
if A[mid] < A[j]{
if target > A[mid] && target <= A[j]{
i = mid+1
}else{
j = mid-1
}
}else{
if target >= A[i] && target < A[mid]{
j = mid-1
}else{
i = mid+1
}
}
}
return false
}
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信740 次点击
下一篇:Go语言实战流媒体视频网站
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
81. 搜索旋转排序数组 II
解题思路
二分的变形,我们之前二分查找基于这样的一个假设:我们定位到一个元素后,这个元素的前后分别都是单调的。
但是这边的数组是旋转的。
所以我们需要修改的是判定逻辑
- 如果我们可以判定出来 那边是旋转的,那边是自增的。则可以通过边界判断
- 如果不行,则进行递归。
代码实现
func search(nums []int, target int) bool {
i,j := 0,len(nums)-1
A := nums
for i<=j{
mid := (i+j)/2
if A[mid]==target{
return true
}
if (A[mid]==A[j]||A[mid]==A[i]) && (search(nums[mid+1:j+1],target) || search(nums[i:mid],target)){
return true
}
if A[mid] < A[j]{
if target > A[mid] && target <= A[j]{
i = mid+1
}else{
j = mid-1
}
}else{
if target >= A[i] && target < A[mid]{
j = mid-1
}else{
i = mid+1
}
}
}
return false
}