Leetcode33. 搜索旋转排序数组

2021年4月14日 597点热度 1人点赞 0条评论

题目描述

整数数组 nums 按升序排列,数组中的值 互不相同

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1

示例 1:

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

示例 2:

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

示例 3:

输入:nums = [1], target = 0
输出:-1

提示:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -10^4 <= target <= 10^4

解题思路

这道题一看按升序排列,就首先想到了二分法。但是其中有部分连续序列是经过旋转处理的,整体就不再是有序的了,那么我们还能使用二分法么?

答案是肯定的(不行也要创造条件上!)。这道题的一个难点就是得观察得出:当整个序列从mid出分为两部分后,总有一部分是有序的。据此,我们考虑使用二分法来解答这道题。

具体的过程如下:

  1. 如果左半部分有序
  • 如果target处于左半部分中,那么只需在左半部分中二分查找;
  • 如果target不在左半部分中,那么在后半部分查找即可;
  1. 如果后半部分有序
  • 如果target处于右半部分中,那么只需在右半部分中二分查找;
  • 如果target不在右半部分中,那么在左半部分查找即可。

根据思路,我们可以得出相应的代码。

示例代码

  1. 递归版本
int research_run(vector<int>&nums,int target,int left,int right)
{
    int mid=(left+right)/2;
    if(target==nums[mid]) return mid;
    if(left==right&&nums[left]!=target) return -1;
    if(nums[left]<nums[mid])
    {
        if(nums[left]<=target&&target<=nums[mid])
        {
            return research_run(nums,target,left,mid-1);
        }
        else{
            return research_run(nums,target,mid+1,right);
        }
    }
    else{
        if(nums[mid]<=target&&target<=nums[right])
        {
            return research_run(nums,target,mid+1,right);
        }
        else{
            return research_run(nums,target,left,mid-1);
        }
    }
}

int search(vector<int>&nums,int target)
{
    return research_run(nums,target,0,nums.size()-1);

}

这个版本在本地IDE显示答案正确,但是提交显示超时。所以,对代码进行了进一步的简化:将能合并的逻辑判断进行了合并,得到了AC的递归版本:

int research_run(vector<int>&nums,int target,int left,int right)
{
    int mid=(left+right)/2;
    if(target==nums[mid]) return mid;
    if(left==right&&nums[left]!=target) return -1;
    if(nums[left]<nums[mid]&&nums[left]<=target&&target<=nums[mid])
    {
       return research_run(nums,target,left,mid-1);
    }
    else if(nums[left]>nums[mid]&&!(nums[mid]<=target&&target<=nums[right]))
    {
        return research_run(nums,target,left,mid-1);
    }
    else{
        return research_run(nums,target,mid+1,right);
    }
}

int search(vector<int>&nums,int target)
{
    return research_run(nums,target,0,nums.size()-1);

}
  1. 迭代版本

将递归版本改为迭代版本如下:

int search(vector<int>&nums,int target)
{
    return research_run(nums,target,0,nums.size()-1);

}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论