Leetcode81. Search in Rotated Sorted Array II

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.

考虑这样的例子：[1,3,1,1,1]，如果使用昨天的代码：

我的代码：按照昨天的代码修改一下

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-81
//T(n)=O(logn), S(n)=O(1)
class Solution {
    public:
    int search(const vector<int> &nums, int target)
    {
        int lo = 0;
        int hi = nums.size() - 1;
        while (lo <= hi)
            {
                int mid = (lo + hi) / 2;
                if (nums[mid] == target) return true;
                if (nums[lo] < nums[mid]) //把这里改成nums[lo] < nums[mid],[lo,mid]一定有序
                    {
                        if (target >= nums[lo] && target < nums[mid])
                            {
                                hi = mid - 1;
                            }
                        else
                            {
                                lo = mid + 1;
                            }
                    }
                else if (nums[lo] > nums[mid]) //[lo,mid]一定无序，[mid,hi]一定有序
                    {
                        if (target > nums[mid] && target <= nums[hi])
                            {
                                lo = mid + 1;
                            }
                        else
                            {
                                hi = mid - 1;
                            }
                    }
                else //nums[lo] == nums[mid]
                {
                    ++lo;//跳过与nums[mid]重复的nums[lo]
                }
            }
        return false;
    }
};

修改使其符合$C++11$标准

class Solution {
    public:
    int search(const vector<int> &nums, int target)
    {
        if(nums.empty()) return false;
        decltype(nums.size()) lo = 0;
        auto hi = nums.size() - 1;
        while (lo <= hi)
            {
                auto mid = (lo + hi) / 2;
                if (nums[mid] == target) return true;
                if (nums[lo] < nums[mid]) //把这里改成nums[lo] < nums[mid],[lo,mid]一定有序
                    {
                        if (target >= nums[lo] && target < nums[mid])
                            {
                                hi = mid - 1;
                            }
                        else
                            {
                                lo = mid + 1;
                            }
                    }
                else if (nums[lo] > nums[mid]) //[lo,mid]一定无序，[mid,hi]一定有序
                    {
                        if (target > nums[mid] && target <= nums[hi])
                            {
                                lo = mid + 1;
                            }
                        else
                            {
                                hi = mid - 1;
                            }
                    }
                else //nums[lo] == nums[mid]
                {
                    ++lo;//跳过与nums[mid]重复的nums[lo]
                }
            }
        return false;
    }
};