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

阅读数:81 次 2019-08-05

字数统计: 441字 | 阅读时长: 2分

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
(例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2])。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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

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

思路

这道题与前面做过的题 LeetCode 33. 搜索旋转排序数组类似, 唯一条件不同地方在旋转数组中可能存在重复元素, 比如极端一点的情况[0,0,5,0,0,0,0], 那么nums[low] == nums[mid], 我们无法判断mid是在旋转点前面还是后面,.
例如 [0,0,0,0], [0,0,5], 无法判断是[0,0,0,0]移到[0,0,5]后面, 还是[0,0,5]移到[0,0,0,0]前面
但是此时nums[low] != target, 我们去掉nums[low] (low++) 这个元素来缩小区间, 最坏情况的时间复杂度为O(n).

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return false;
        int length = nums.length;
        int high = length - 1;
        int low = 0;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(target == nums[mid]) 
                return true;
            if(nums[mid] < nums[low]){
                if(target > nums[mid] && target <= nums[high]){
                    low = mid + 1;
                }else {
                    high = mid - 1;
                }
            }else if(nums[mid] > nums[low]){
                if(target >= nums[low] && target < nums[mid]){
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            }else{
                ++low;
            }
        }
        return false;
    }
}