LeetCode 81.搜索旋转排序数组II题目链接:
https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
题目描述:
已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false 。
示例 1:
输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true
示例 2:
输入:nums = [2,5,6,0,0,1,2], target = 3
输出:false
提示:
1. 1 <= nums.length <= 5000
2. -104 <= nums[i] <= 104
3. 题目数据保证 nums 在预先未知的某个下标上进行了旋转
4. -104 <= target <= 104
题目分析:
这道题我们可以直接使用暴力法,遍历数组,如果有元素与目标值相同,则返回true,否则返回false(见题解一)。我们也可以使用二分查找法,我们先定义左右边界,左边界初始化为数组头,右边界初始化为数组尾,当左边界小于等于右边界时执行循环,获取当前区间中点值,如果中点值刚好等于目标值,说明查找到目标值,返回true。如果左边界值等于中点值,无法判断哪个区间是递增的,我们可以微调区间,左边界向右移动一位,再进行下一轮判断。如果中点值小于等于右边界值,说明右区间递增,同时,如果目标值大于中点值且目标值小于等于右边界值,左边界更新至中点右一个元素;否则目标值小于中点值,右边界更新至中点左一个元素。如果中点值大于左边界值,说明左区间递增,同时,如果目标值大于等于左边界值且目标值小于中点值,右边界更新至中点左一个元素;否则左边界更新至中点右一个元素。如果遍历完还没有找到目标值,返回false。
题解一(暴力法):
执行用时: 1 ms
内存消耗: 37.6 MB
class Solution {
public boolean search(int[] nums, int target) {
// 获取数组中元素的值
for (int x : nums)
// 如果数组中有一个元素值刚好与目标值相等
if (x == target)
// 返回true
return true;
// 数组中找不到目标元素,返回false
return false;
}
}
题解二(二分查找法):
执行用时: 1 ms
内存消耗: 37.7 MB
class Solution {
public boolean search(int[] nums, int target) {
// 定义左右边界
int left = 0, right = nums.length - 1;
// 当左边界小于等于右边界时执行循环
while (left <= right) {
// 获取区间中点值
int mid = (left + right) / 2;
// 如果中点值刚好等于目标值,说明查找到目标值,返回true
if (nums[mid] == target)
return true;
// 如果左边界值等于中点值,无法判断哪个区间是递增的
if (nums[left] == nums[mid])
// 移动左边界
++left;
// 如果中点值小于等于右边界值,说明右区间递增
else if (nums[mid] <= nums[right])
// 如果目标值大于中点值且目标值小于等于右边界值
if (target > nums[mid] && target <= nums[right])
// 左边界更新至中点右一个元素
left = mid + 1;
// 否则目标值小于中点值
else
// 右边界更新至中点左一个元素
right = mid - 1;
// 如果中点值大于左边界值,说明左区间递增
else
// 如果目标值大于等于左边界值且目标值小于中点值
if (target >= nums[left] && target < nums[mid])
// 右边界更新至中点左一个元素
right = mid - 1;
else
// 左边界更新至中点右一个元素
left = mid + 1;
}
// 没有找到目标值,返回false
return false;
}
}
题目来源:力扣(LeetCode)