旋转数组 => 有序数组查找 taget
解题思路
先根据 153 的题解，
nums[mid] > nums[right]由此可以将数组分为升序的两段，判断出 mid 是在左段还是右段；再判断 target 是在 mid 的左边还是右边，从而调整左右边界 left 和 right ，对升序数组进行二分查找即可；
复杂度
-
时间复杂度：
O(logn) -
空间复杂度：
O(1)
实现代码
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
}
// 先根据 nums[mid] 与 nums[right] 的关系判断 mid 是在左段还是右段
if (nums[mid] >= nums[right]) { // mid 在左段
// 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 left 和 right
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在 mid 左边
} else {
left = mid + 1; // target 在 mid 右边
}
} else { // mid 在右段
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
};
旋转数组 构造成 有序数组
解题思路
对于旋转数组
nums = [4,5,6,7,0,1,2]
- 首先根据 nums[0] 与 target 的关系判断 target 是在左段还是右段；
- 例如
target = 5, 目标值在左半段，因此在[4, 5, 6, 7, inf, inf, inf]这个有序数组里找就行了；- 例如
target = 1, 目标值在右半段，因此在[-inf, -inf, -inf, -inf, 0, 1, 2]这个有序数组里找就行了；如此，又将「旋转数组中找目标值」 转化成了 「有序数组中找目标值」
复杂度
-
时间复杂度：
O(logn) -
空间复杂度：
O(1)
代码实现
var search = function (nums, target) {
let left = 0;
let right = nums.length;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
}
if (target >= nums[0]) {
// target 在左段时，若 mid 在右半段，则将 mid 索引的值改成 Infinity
if (nums[mid] < nums[0]) {
nums[mid] = Infinity;
}
} else {
// target 在右段时，若 mid 在左半段，则将 mid 索引的值改成 -Infinity
if (nums[mid] >= nums[0]) {
nums[mid] = -Infinity;
}
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
73.矩阵置零
上一篇
评论
