LeetCode 0033 - Search in Rotated Sorted Array
# Hints
- 思维 + 二分查找 + 分类讨论
# 题面
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,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
You are given a target value to search. If found in the array return its index, otherwise return .
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of .
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
# 题意
给定一个长为 的数组 ,该数组是由一个长为 的严格递增数组 旋转而来,即 ,而且旋转位置 是未知的。
给定一个整数 ,要求在 的时间内判断 在 内是否存在,如果存在则返回其位置下标,否则返回 。
输入保证 中不存在重复元素。
# 题解
容易想到用二分查找来解决问题,然而现在的数组是旋转过的,且不知道旋转点的位置,似乎不能直接进行二分。
事实上,旋转过后仍然可以进行二分查找,只是麻烦了些。
我们以 为例,观察其所有可能的旋转:
---|---
1234567
7123456 -> 7 123456
6712345 -> 67 12345
5671234 -> 567 1234
4567123 -> 4567 123
3456712 -> 34567 12
2345671 -> 234567 1
首先,除了 的情况以外,旋转后的数组可以被划分为两段连续单调序列,这是很显然的。
现在,我们考虑 的落点和这两段区间的关系,显然 要么落在左侧区间、要么落在右侧区间,即 或 。
上述两种情况显然是对称等价的,所以我们只以 落在左侧区间的情况为例解释。
可以发现,当 时,必有 ,否则必有 。
至于 的情况,自然是直接返回答案了。
因此分类讨论二分即可。
下面给出了两份代码实现,本质上相同,但前者的常数时间较差,原因是后者通过对 和 的特判缩小了迭代次数。二者最坏时间复杂度没有差别。
细节问题:
注意特判空数组的情况,或在初始化时注意令 而不是令 。
如果不对 和 进行特判,注意 落在左侧区间的条件是 而不是 。
# AC代码(1)
class Solution {
public:
int 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) {
return mid;
}
// 分类讨论
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 -1;
}
};
# AC代码(2)
class Solution {
public:
int 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) {
return mid;
}
if (nums[left] == target) {
return left;
}
if (nums[right] == target) {
return right;
}
// 分类讨论
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 -1;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01