leetcode第一刷_Search in Rotated Sorted Array
2024-08-30 22:16:47
旋转数组的查找问题。从头開始扫一遍。O(N)的复杂度,一般也能过,甚至先排序下面,再二分都能过。只是这道题的目的当然不在于此。
想一下旋转之后对我们的查找产生了什么影响。假设没旋转过,我们直接比較target与A[middle]的大小,然后总能很确定的丢掉源数组的一半。即把搜索空间减半,可是旋转之后,仅仅依据A[middle]是确定不了下一轮的走向的,由于即使A[middle]比target大,按理说我们应该往前找,可是假设源数组是循环左移的。较小的数可能在后半部分。
上面说的都是旋转之后与没旋转的差别,这个是非常easy想明确的,关键是旋转之后有什么没有变化呢?答案是不管怎么旋转,middle的左右部分肯定至少有一个是全然有序的。这个应该好理解。
怎么推断这一半是哪一半也非常简单。仅仅要看A[middle]跟A[0]和A[N]的大小关系就能够了。假设有序,我们就能够通过比較端点与target的大小来确定target应不应当在这一部分,假设不在的话,就递归查询还有一半。依据这个策略,就能够每次确定的丢掉一半了。时间复杂度也就降下来了。
不要忘记这个题有非常强的如果,数组中没有反复的元素,有反复元素的非常不一样。是下一道题的内容。
int msearch(int A[], int n, int target, int* a){
if(n<=0)
return -1;
int middle = n/2;
if(A[middle] == target)
return A-a+middle;
if(A[middle]>target){
if(A[0]<=target||A[0]>A[middle]){
return msearch(A, middle, target, a);
}else{
return msearch(A+middle+1, n-middle-1, target, a);
}
}else{
if(A[0]<=A[middle]||A[n-1]>=target)
return msearch(A+middle+1, n-middle-1, target, a);
else{
return msearch(A, middle, target, a);
}
}
} class Solution {
public:
int search(int A[], int n, int target) {
return msearch(A, n, target, A);
}
};
最新文章
- Mac 效率工具
- Intelij IDEA 2016.3安装mybatis插件并激活教程
- DefaultFilesMiddleware中间件如何显示默认页面
- TCP/IP详解 学习六
- ScrollView与ListView的冲突
- ease of rerouting traffic in IP networks without readdressing every host
- tostring() 作用
- nginx设置不使用缓存 add_header Cache-Control no-cache
- mysql 和 mongo db 语法对比
- 音频播放器在chrome浏览器,play报错
- sql server 备份与恢复系列四 大容量模式下的备份与还原
- springboot aop 自定义注解方式实现完善日志记录(完整源码)
- ASP.NET Core Razor Pages
- 7.13python多进程
- JDBC编程的步骤
- kafka的API操作
- Scala--操作符
- Java Web项目--使用JSP生成一个页面
- Android开发——View的生命周期总结
- 【转】C++操作符的优先级 及其记忆方法