X

LEETCODE 33. Search in Rotated Sorted Array 解题思路分析

题目大意:

搜索旋转排序数组

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

( 例如,数组 [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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=33

解题思路分析:

本题要求使用logn的时间复杂度来解题,也就是说必须使用二分查找的思路。如果数组没有被旋转,本题则是二分查找的典型模板题目。考虑到数组被旋转过,本题就变得稍微复杂了一点,但思路并不难。我们先找到数组被旋转后的规律,举个例子,数组[1,2,3,4,5,6,7]被旋转为:

[6,7,1,2,3,4,5]

其中红色的数字是被旋转后未按照升序排序的部分,即使这样我们仍然可以使用二分法,取得数组的中间位置上的数字2,考虑一下,如果数组没被旋转,处于中间位置上的数字2,一定会大于等于区间最左边的数,并且一定小于等于区间最右边的数。但数组被旋转之后,上述两个已知条件只剩下一个能被满足,能被满足的那半个区间一定是按照升序顺序排序的区间,例如上面的例子中,满足条件的合法区间是[mid, right](2,3,4,5)。

此时我们判断target的值是否在合法区间内( target >=nums[mid] && target <=nums[right] ),如果在该区间内,我们在该区间二分查找即可。如果不在,说明target在另外半个非法排序区间内,此时,将left和right值更新为另外半个区间的坐标。继续二分该区间,查看哪半个区间是排序好的合理区间,并查看target是否在该合理区间内,在的话,开始常规二分查找,否则继续循环上述步骤即可。

实现代码:

public int search(int[] nums, int target) {
    // 左指针为0,右指针为数组长度减一
    int left=0, right=nums.length-1;
    // 二分当前区间
    while(left<=right){
        // 中间位置
        int mid=(left+right)/2;
        // 如果中间位置的数小于等于区间最右边的数
        // 那么[mid, right]是合理排序区间
        if(nums[mid]<=nums[right]){
            // 如果target不在该合理区间内,查询区间更改为另外半个区间
            if(target<nums[mid]||target>nums[right]){
                right=mid-1;
                continue;
            }
        }
        // 如果中间位置的数大于等于区间最左边的数
        // 那么[left, mid]是合理排序区间
        else if(nums[mid]>=nums[left]){
            // 如果target不在该合理区间内,查询区间更改为另外半个区间
            if(target<nums[left]||target>nums[mid]){
                left=mid+1;
                continue;
            }
        }
        // 确保target在当前合理排序区间内时,开始常规二分查找
        if(nums[mid]==target) return mid;
        if(nums[mid]>target) right=mid-1;
        else left=mid+1;
    }
    return -1;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.

Memory Usage: 40.7 MB, less than 5.66% of Java online submissions for Search in Rotated Sorted Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-33-search-in-rotated-sorted-array-解题思路分析/
Categories: leetcode
kwantong: