描述

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.

分析

如果允许重复，那么上一题中“若A[first] <= A[mid]，则[first,mid]区间有序”的假设就不成立了，比如可能存在旋转后形如[1,3,1,1,1]的数组。

显然，如果A[first]<=A[mid]不能确定是否有序，就把这个条件细分一下：

若A[first] < A[mid]，就一定递增；
若A[first] == A[mid]，则确定不了，就将first加1，往下看一步即可。

代码如下：

class Solution{

public:

    int search(int A[],int n,int target){

        int first = 0,last = n;

        const int mid = (first + mid) / 2;  //note that mid is const,which means that we would not modify the value of mid before a new loop starts

        while(first != mid){

            if(A[mid] == target)

                return mid;

            if(A[first] < A[mid]){

                if(A[first] <= target && target < A[mid])

                    last = mid;

                else

                    first = mid + 1;

            }

            else if(A[mid] == A[first])

                ++first;    //skip duplicatted one

            else{

                if(A[mid] <= target && target <= A[last - 1])

                    first = mid + 1;

                else

                    last = mid;

            }

        }

        return -1;

    }

}

巴特西

leetcode解题报告（4）：Search in Rotated Sorted ArrayII

描述

分析

最新文章

热门文章