首页 > 代码库 > leetcode第一刷_Search in Rotated Sorted Array II
leetcode第一刷_Search in Rotated Sorted Array II
接着上一篇,同样是旋转数组中查找问题。如果这个数组有重复元素怎么办呢?会有什么影响?
我举一个极端的例子,假设数组中的元素是这样的,1,1,2,1,1,1,1,我们要在这个数组中查找2,一开始的A[middle]=1,发现比target小,那我们就看看A[0]和A[N],发现都跟A[middle]相等,那么这个2到底在哪一半中?只有上帝知道,如果他老人家真的存在的话。这种时候我们怎么办呢?没有其他的办法,只能从头开始乖乖的扫描,直到发现target或者确定他不存在。
为什么会出现这种情况,或者说包含重复元素跟不包含重复元素在本质上有什么区别呢?这种区别又是怎样影响复杂度的呢?我觉得区别在于,当A[middle]与两头的元素相等时,我们没法找到一半有序的元素,因此我们也就没法通过比较边界来确定target在不在这一半元素之中,也就是我们在每一轮的判定中,无法确定的扔掉一半元素,最坏情况下的复杂度自然就提高到了O(N)。
编码上没有太大的区别,只要当与两头元素都相等时,就只移动左边的指针,逐个扫描过来,需要注意的是,每次移动时要判定这个值是否跟target的相等。
class Solution { public: bool search(int A[], int n, int target) { int l = 0, r = n-1, mid; while(l<=r){ mid = (l+r)/2; if(A[mid] == target) return true; if(A[l]<A[mid]){ if(target>=A[l]&&target<A[mid]) r = mid-1; else l = mid+1; }else if(A[mid]<A[r]){ if(target>A[mid]&&target<=A[r]) l = mid+1; else r = mid-1; }else{ if(A[l] == target) return true; else l++; } } return false; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。