LeetCode:Search in Rotated Sorted Array II

接前一题(Search in Rotated Sorted Array),但数组中的元素允许重复。
LeetCode OJ地址:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
关键点:旋转前数组有序,可能有重复元素。


我的解法:
前一题能利用折半查找思想的关键是旋转后数组分为两个有序子区间,可以通过A[first]A[mid]A[last-1]target的大小测试来快速缩小查找范围。由于本题中数组可能有重复元素,如对于数组[1,3,1,1,1]A[first]=A[mid]=A[last-1]=1,此时将无法确定是应该将查找区间搜小到A[first,mid)还是A[mid+1,last)。
因此,算法加入高亮代码行17和18的判断,当这三个元素相等时,只++first
注:search返回值由位置索引int修改为是否存在标识bool

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool search(int A[], int n, int target) {
        int first = 0;
        int last = n;
        while (first != last) {
            int mid = (first+last)/2;
            if (target == A[mid])
                return true;
            /*
             * 由于可以有重复元素
             * A[first],A[mid],A[last-1]可能相等
             * 此时不能确定[first,mid)或[mid+1,last)是否是有序子区间
             * 如数组 [1,3,1,1,1]
             */
            if (A[first] == A[mid]
                    && A[mid] == A[last-1]) {
                ++first;
            }
            else if (A[first] <= A[mid]) {
                if (A[first] <= target && target < A[mid])
                    last = mid;
                else
                    first = mid+1;
            }
            else {
                if (A[mid] < target && target <= A[last-1])
                    first = mid+1;
                else
                    last = mid;
            }
        }
        return false;
    }
};

参考解法:
算法通过将前一题中的A[first] <= A[mid]判断分裂为A[first] < A[mid]A[first] == A[mid]。当A[first] < A[mid]时必能正确缩小到某个子区间,而当A[first] == A[mid]时只通过++first进行更新。

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool search(int A[], int n, int target) {
        int first = 0;
        int last = n;
        while (first != last) {
            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
                ++first;
        }
        return false;
    }
};

发表评论

电子邮件地址不会被公开。