首页 > ACM题库 > LeetCode > LeetCode-Search in Rotated Sorted Array II[数组]
2014
11-18

LeetCode-Search in Rotated Sorted Array II[数组]

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.

标签: Array Binary Search
分析

允许重复元素,则上一题中如果{A[m]>=A[l]},那么{[l,m]}为递增序列的假设就不能成立了,比如{[1,3,1,1,1]}。

如果{A[m]>=A[l]}不能确定递增,那就把它拆分成两个条件:

\item 若{A[m]>A[l]},则区间{[l,m]}一定递增
\item 若{A[m]==A[l]} 确定不了,那就{l++},往下看一步即可。

代码1

// LeetCode, Search in Rotated Sorted Array II
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool search(int A[], int n, int target) {
        int first = 0, last = n;
        while (first != last) {
            const int mid = (first + last) / 2;
            if (A[mid] == target)
                return true;
            if (A[first] < A[mid]) {
                if (A[first] <= target && target < A[mid])
                    last = mid;
                else
                    first = mid + 1;
            } else if (A[first] > A[mid]) {
                if (A[mid] < target && target <= A[last-1])
                    first = mid + 1;
                else
                    last = mid;
            } else
                //skip duplicate one
                first++;
        }
        return false;
    }
};

Java代码:

public class Solution {
    public static boolean search(int[] A, int target) {
        return searchBinary(A, 0, A.length-1 , target);
    }

    public static boolean searchBinary(int A[],int s,int e,int target){
        int mid = (s+e)/2;

        if(A[mid] == target)
            return true;
        if(s >= e) return false;
        if( A[mid] < A[e] ){ //后半部分是顺序的
            if(target > A[mid] && target <= A[e]){
                return searchBinary(A, mid+1, e, target);
            }else
                return searchBinary(A, s, mid-1, target);
        }else if(A[mid] > A[e]){ //前半部分顺序的
            if(target >= A[s] && target < A[mid])
                return searchBinary(A, s, mid-1, target);
            else
                return searchBinary(A, mid+1, e, target);
        }else{ //相等时,无法判断
            for(int i=s; i<=e; i++)
                if(A[i] == target) return true;
            return false;
        }

    }
}

相关题目
Search in Rotated Sorted Array


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 是穷举,但是代码有优化(v数组),并不是2^n。测试数据应该没问题,之前有超时的代码。

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.