LeetCode 81. 搜索旋转排序数组 II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 81. 搜索旋转排序数组 II 原题链接中等

作者：

小呆呆 , 2020-07-15 22:35:24 , 所有人可见 , 阅读 639

题目描述

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

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

样例

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

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

进阶:

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

算法分析

由于二分最坏情况下的时间复杂度是$O(n)$，因此对整个数组线性扫描一遍，是否能找到target

时间复杂度 $O(n)$

Java 代码

class Solution {
    public boolean search(int[] nums, int target) {
        for(int i = 0;i < nums.length;i ++)
            if(nums[i] == target)
                return true;

        return false;
    }
}

5 评论

YYC 2020-07-15 23:11

class Solution {
    public boolean search(int[] nums, int target) {

        int n = nums.length;
        if (n == 0) return false;

        // 1. 去除尾部的临界值
        int R = n - 1;
        while (R > 0 && nums[R] == nums[0]){
            R--;
        }

        // 2. 找到分界点
        int l = 0, r = R;
        while (l < r){
            int mid = l + r + 1>> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 3. 确定升序区间
        if (target >= nums[0]){
            // left
            l = 0;
        } else {
            // right
            l = r + 1;
            r = R;
        }

        // 4. 找目标值
        while (l < r){
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return nums[r] == target;
    }
}