LeetCode 0081 - Search in Rotated Sorted Array II
# Hints
- 思维 + 二分查找 + 分类讨论
# 前置题目
LeetCode 0033 - Search in Rotated Sorted Array
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
This is a follow up problem to
Search in Rotated Sorted Array
, where nums may contain duplicates.Would this affect the run-time complexity? How and why?
# 题意
给定一个长为 的数组 ,该数组是由一个长为 的严格递增数组 旋转而来,即 ,而且旋转位置 是未知的。
给定一个整数 ,要求在尽可能短的时间内判断 在 内是否存在。
# 题解
本题和 LeetCode 0033 的区别在于数组中可能存在重复元素,这导致二分查找无法区分 [1,1,1,3,1]
和 [1,3,1,1,1]
两种情况。题解普遍使用暴力的方法来处理此类情况,类似于:
if (nums[left] == nums[mid]) {
left ++;
continue;
}
这导致在最坏情况下时间复杂度将退化为 。所以我觉得这题出得挺没意思的,我也懒得优化常数了。
# AC代码
class Solution {
public:
bool search(vector<int> & nums, int target) {
// 二分查找
int left = 0, right = (int)nums.size() - 1;
while (left <= right) {
// 获取中间点
int mid = (left + right) / 2;
// 找到的情况
if (nums[mid] == target || nums[left] == target || nums[right] == target) {
return true;
}
// 暴力
if (nums[left] == nums[mid]) {
left ++;
continue;
}
// 分类讨论
if (nums[left] < nums[right]) {
if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] > nums[left]) {
if (target > nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target < nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
// 返回
return false;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01