【Leetcode 每日一题】81. 搜索旋转排序数组 II

问题背景

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

解题过程

这题是在 搜索旋转排序数组 的基础上增加了元素可重复这个条件，仍然可以参考无重复元素的实现，先找到最小值，再到相应的部分数组中去找结果。
然而之前的二分答案法是每次与数组的最后一个元素比较大小，如果遇到当前元素与数组中最后一个元素重复的情况，就没有办法确定要往那个方向继续执行了。
考虑到如果有重复元素出现上述情况，它们会在旋转之后分布在数组两头。
这时候可以反复比较范围左边界的元素和数组中最后一个元素，发现重复时就将范围中的首个元素去掉。
可能会出现两种情况，去掉的这个是要查找的目标，那它还有一个重复值在数组末尾，不影响结果；去掉的这个不是要查找的目标，那就无所谓了，也不影响结果。

这道题属于是经典的为了考知识点而一味地加限制，评价为出题把脑子出坏了。
道理很简单，去掉重复元素使得范围上可用二分查找这个过程，时间复杂度是 $O(N)$ 这个量级的。
这就导致了，整个算法是无法达到 $O(logN)$ 这样的水平了。
既然如此，还费劲巴拉的二分什么二分，直接遍历数组同样也只是需要 $O(N)$ 的时间。

具体实现

二分查找

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        // 去掉二分范围内首尾的重复元素，注意 left != n - 1 这个条件，别把所有元素都去掉了
        while (left != n - 1 && nums[left] == nums[n - 1]) {
            left++;
        }
        // Leetcode 33.搜索旋转排序数组
        int minIndex = findMin(nums, left, right);
        if (target > nums[n - 1]) {
            return binarySearch(nums, target, 0, minIndex);
        }
        return binarySearch(nums, target, minIndex, n);
    }

    // Leetcode 153.找到数组中的最小值
    private int findMin(int[] nums, int left, int right) {
        int n = nums.length;
        while(left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > nums[n - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // Leetcode 35.搜索插入位置
    private boolean binarySearch(int[] nums, int target, int left, int right) {
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target;
    }
}

直接遍历

class Solution {
    public boolean search(int[] nums, int target) {
        for (int num : nums) {
            if (num == target) {
                return true;
            }
        }
        return false;
    }
}