`

LeetCode - Search in Rotated Sorted Array II

 
阅读更多

Follow up for "Search in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

因为rotate的缘故,当我们切取一半的时候可能会出现误区,所以我们要做进一步的判断。具体来说,假设数组是A,每次左边缘为l,右边缘为r,还有中间位置是m。在每次迭代中,分4种情况:
(1)如果target==A[m],那么m就是我们要的结果,直接返回;
(2)如果A[m]<A[r],那么说明从m到r一定是有序的(没有受到rotate的影响),那么我们只需要判断target是不是在m到r之间,如果是则把左边缘移到m+1,否则就target在另一半,即把右边缘移到m-1。
(3)如果A[m]>A[r],那么说明从l到m一定是有序的,同样只需要判断target是否在这个范围内,相应的移动边缘即可。

(4)如果A[m]==A[r], 确定不了,那就r--,往下看一步即可。

 

算法的平均时间复杂度为O(logn)。最坏情况(比如全部都是一个元素,或者只有一个元素不同于其他元素,而他就在最后一个)就会出现每次移动一步,总共是n步,算法的时间复杂度变成O(n)。

 

public boolean search(int[] A, int target) {
    int l=0, r=A.length-1;
    while(l<=r) {
        int m = (l+r)>>1;
        if(A[m] == target) return true;
        if(A[m]<A[r]) {
            if(target>A[m] && target<=A[r]) {
                l = m+1;
            } else {
                r = m-1;
            }
        } else if(A[m]>A[r]){
            if(target>=A[l] && target<A[m]) {
                r = m-1;
            } else {
                l = m+1;
            }
        } else {
            r--;
        }
    }
    return false;

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics