旋转数组 构造成 有序数组
解题思路
题目与 33. 搜索旋转排序数组 区别是增加了重复项；
那我们先根据 153 的题解，
nums[mid] > nums[right]由此可以将数组分为升序的两段，判断出 mid 是在左段还是右段；判断出在左段和右段之后，要判断当前段是不是 递增序列 ，如果 mid 的值与 left 或 right 的值相同，则向中间收缩一位，直到构建出一个 递增序列 为止；
再判断 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 true;
}
// 去掉重复项
if (nums[mid] === nums[left]) {
left++;
} else if (nums[right] === nums[mid]) {
right--;
} else if (nums[mid] >= nums[right]) {
// 先根据 nums[mid] 与 nums[right] 的关系判断 mid 是在左段还是右段
// 左边
// 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 left 和 right
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在左边
} else {
left = mid + 1; // target 在右边
}
} else { // 右边
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 33. 搜索旋转排序数组
上一篇
评论
