T11-搜索旋转排序数组

木又AI帮

发布于 2019-07-18 16:53:03

3360

发布于 2019-07-18 16:53:03

这是木又陪伴你的第18天

今天分享leetcode第11篇文章，也是leetcode第33题—Search in Rotated Sorted Array（搜索旋转排序数组），地址是：https://leetcode.com/problems/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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

【中文题目】

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

【思路】

如果没有时间复杂度的限制，那么可以直接暴力求解，遍历数组查找target即可。

现在时间复杂度限制在O(log n)，可以自然地想到用二分查找的变形。

如果你看过上一篇文章（寻找旋转排序数组中的最小值），自然可以想到一种方法：首先寻找最小值，然后由于最小值左右两个区间都是排序数组，因此使用二分查找即可。

有没有更加简单的方法？

我们知道，数组l -> mid和mid -> r这两个区间有一个特点：肯定有一个区间是有序的。

那么我们是否可以根据这个特点选择某一个区间或者排除某一个区间？

这个想法是可行的。

如果nums[mid] < nums[r]，说明mid -> r这个区间是有序的。如果target存在于mid -> r区间，必定满足条件：nums[mid] < target <= nums[r]。否则target存在于l -> mid区间或者不存在。

同理，如果nums[mid] > nums[r]，说明nums[mid] > nums[l]， l -> mid区间是有序的。如果target存在于l -> mid区间，必定满足：nums[l] <= target < nums[mid]。否则target存在于mid -> r区间或者不存在。

【代码】

python版本

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        l, r = 0, length - 1
        if length < 1:
            return -1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid

            # mid -> r有序
            if nums[mid] < nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1

            # l -> mid有序
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1

        return -1

C++版本

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] == target)
                return mid;

            // mid -> r有序
            if(nums[mid] < nums[r]){
                if(nums[mid] < target && target <= nums[r])
                    l = mid + 1;
                else
                    r = mid - 1;
            //l -> mid 有序
            }else{
                if(nums[l] <= target && target < nums[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        }
        return -1;
    }
};

【总结】