欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II

程序员文章站 2022-07-16 12:57:46
...

###LeetCode 33. Search in Rotated Sorted Array
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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

这道题是二分查找的变体。一个不含重复数字的有序数组,可能经过旋转(0 1 2 4 5 6 7 可能变成了 4 5 6 7 0 1 2),在数组中查找一个目标值。这道题的难点在于我们不知道原数组在哪旋转了。

二分搜索的关键在于获得中间数之后,还要判断接下来的搜索是在前半段还是后半段。数组的旋转情况可以大致分为以下三种情况:
LeetCode 33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II
可以看到,前半段或者后半段之中必定有一段是有序的。如果中间数大于最左边数,那么前半段是有序的;如果中间数小于最左边数,那么后半段是有序的。虽然数组经过旋转给二分搜索范围的确定带来困难,但可以利用目标值是否在有序的半段区域内 来确定下一次搜索的范围。

int search(vector<int>& nums, int target) {
        int size = nums.size();
        int low = 0, high = size - 1, mid;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (nums[low] <= nums[mid])
            {
                if (target < nums[mid] && target >= nums[low]) high = mid - 1;
                else if (target == nums[mid]) return mid;
                else low = mid + 1;
            }
            else
            {
                if (target > nums[mid] && target <= nums[high]) low = mid + 1;
                else if (target == nums[mid]) return mid;
                else high = mid;
            }
        }
        return -1;
    }

LeetCode 81. 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?
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.
这道题是Search in Rotated Sorted Array 的扩展,不同之处在于允许有序数组可能含有重复的元素。思路大致方向还是相同的,比较中间数和最左边的数。但由于可能含有重复元素,所以可能会出现这样的情况:1 1 1 3 1,中间数等于最左边数,要是按照原来的解法,是无法确定下一次搜索的范围。
对于这种情况可以这样处理:把最左值往右移一位,继续迭代,若之后中间数和最左数还是相同则继续移,直到它们不相等为止。

bool search(vector<int>& nums, int target) {
        int size = nums.size();
        int low = 0, high = size - 1, mid;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (nums[mid] == target) return true;
            if (nums[low] < nums[mid])
            {
                if (target < nums[mid] && target >= nums[low]) high = mid - 1;
                else low = mid + 1;
            }
            else if(nums[low] > nums[mid])
            {
                if (target > nums[mid] && target <= nums[high]) low = mid + 1;
                else high = mid;
            }
            else ++low;
        }
        return false;
    }
相关标签: leetcode