【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;}
}