提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode No.81 搜索旋转排序数组 II（二分法）

数组 排序
2023-03-20 14:55:31 时间

一、题目描述

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

进阶：

这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

二、解题思路

使用二分查找，初始化两个变量low=0,hight=nums.length-1

1、mid=(low+high)/2

2、假如nums[mid]等于target，返回下标mid

3、当nums[mid]小于nums[high]时，说明mid->high右侧是有序的，判断target是否在右侧，否则往左侧查找

4、当nums[mid]大于nums[high]时，说明low->mid左侧是有序的，判断target是否在左侧，否则往右侧查找

5、当low>high时，表示没有找到，返回-1

对于数组中有重复元素的情况，二分查找时可能会有 a[l]=a[mid]=a[r]，此时无法判断区间 [l,mid] 和区间[mid+1,r] 哪个是有序的。

例如nums=[3,1,2,3,3,3,3]，target=2，首次二分时无法判断区间 [0,3] 和区间 [4,6] 哪个是有序的。

对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

三、代码

1、递归

class Solution {
    public boolean search(int[] nums, int target) {
        int rs=fun(nums, 0, nums.length - 1, target);
        if(rs==-1){
            return false;
        }else{
            return true;
        }
    }
    private int fun(int[] nums, int low, int high, int target) {
        if (low > high)
            return -1;
        int mid = (low + high) / 2;
        if (nums[mid] == target)
            return mid;
        if(nums[mid]==nums[low]&&nums[mid]==nums[high]){
            low++;
            high--;
            return fun(nums, low, high, target);
        }else if (nums[mid] <= nums[high]) {
            //右侧是有序的
            if (nums[mid] <= target && target <= nums[high])
                //目标值在右侧
                return fun(nums, mid + 1, high, target);
            else
                //目标值在左侧
                return fun(nums, low, mid - 1, target);
        }else{
            //左侧是有序的
            if (nums[low] <= target && target < nums[mid])
                //目标值在左侧
                return fun(nums, low, mid - 1, target);
            else
                //目标值在右侧
                return fun(nums, mid + 1, high, target);
        }
    }
}

2、双指针

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                //左侧是有序的
                if (nums[l] <= target && target < nums[mid]) {
                    //目标值在左侧
                    r = mid - 1;
                } else {
                    //目标值在右侧
                    l = mid + 1;
                }
            } else {
                //右侧是有序的
                if (nums[mid] < target && target <= nums[n - 1]) {
                    //目标值在右侧
                    l = mid + 1;
                } else {
                    //目标值在左侧
                    r = mid - 1;
                }
            }
        }
        return false;
    }
}

四、复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。最坏情况下数组元素均相等且不为 target，我们需要访问所有位置才能得出结果。

空间复杂度：O(1)。

相关文章