LeetCode 81. Search in Rotated Sorted Array II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 81. Search in Rotated Sorted Array II 原题链接中等

作者：

yxc , 2018-05-01 12:02:38 , 所有人可见 , 阅读 2413

题目描述

假设一个升序数组以某个轴做了旋转，但轴的位置是未知的。
例如[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]，在其中检索某个值是否存在。
数组中可能包含相同元素。

样例1

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

样例2

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

算法

(线性扫描) $O(n)$

这道题类似于Search in Rotated Sorted Array，不同点在于这道题里的数组可能包含相同元素。
目前能想到的二分做法的最坏时间复杂度都是 $O(n)$ ，所以索性就拿线性扫描做了^^。

时间复杂度分析：整个数组只扫描一遍，所以时间复杂度是 $O(n)$ 。

C++ 代码

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        for (auto &v : nums)
            if (v == target)
                return true;
        return false;
    }
};

5 评论

T-SHLoRk 2019-07-13 22:12

这是我在别的地方看到的二分题解，没有太搞懂为什么nums[mid] == nums[right]的时候，就是right – 。

bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return false;
        int left = 0, right = n - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return true;
            else if (nums[mid] < nums[right])  // nums[mid] 在右边升序的数据区间内    
            {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else    right = mid - 1;
            }
            else if (nums[mid] > nums[right]) // nums[mid] 在左边升序的数据区间内    
            {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else    left = mid + 1;
            }
            else // nums[mid] = nums[right]
                right--;
        }
        return false;
    }