81.搜索旋转排序数组II(中等)

2024-02-28 22:30:40

题目描述:

已知存在一个按非降序排列的整数数组 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 <= nums.length <= 5000
- 1 0 4 10^{4} 104 <= nums[i] <= 1 0 4 10^{4} 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
- 1 0 4 10^{4} 104 <= target <= 1 0 4 10^{4} 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)

码农公寓