一、题目描述
已知存在一个按非降序排列的整数数组 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:
输入:nums = [2,5,6,0,0,1,2]
, target = 0
输出:true
示例 2:
输入:nums = [2,5,6,0,0,1,2]
, target = 3
输出:false
提示:
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -10^4 <= target <= 10^4
二、解题思路
首先,我们需要找到数组中的最小元素所在的位置,这个位置也就是数组的旋转点。由于数组原本是排序的,旋转后,数组被分为两部分,每部分都是有序的。
我们可以使用二分查找来找到这个旋转点。在二分查找的过程中,如果中间元素大于它后面的元素,则中间元素就是旋转点。否则,如果中间元素小于等于起始元素,说明旋转点在中间元素的右侧;否则,旋转点在中间元素的左侧。
找到旋转点后,我们可以确定目标值位于哪一侧的有序数组中。我们可以再次使用二分查找来查找目标值。
如果在任一次二分查找中找到了目标值,我们返回 true;如果所有查找都未找到目标值,我们返回 false。
三、具体代码
class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int n = nums.length;
int left = 0, right = n - 1;
// 查找旋转的下标点
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
// left现在是旋转的下标点,将数组分为两部分
int start = left;
left = 0;
right = n - 1;
// 确定target在旋转点的哪一侧
if (target >= nums[start] && target <= nums[right]) {
left = start;
} else {
right = start - 1;
}
// 在确定的一侧进行二分查找
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 查找旋转点的二分查找算法的时间复杂度是 O(log n),其中 n 是数组的长度。
- 确定目标值在哪一侧的有序数组中的操作是常数时间复杂度,因为它是基于旋转点的位置来直接确定的。
- 在确定的一侧进行二分查找的时间复杂度也是 O(log n)。
- 因此,总的时间复杂度是 O(log n) + O(log n) = O(log n),因为二分查找是主导整个算法的时间复杂度的部分。
2. 空间复杂度
- 这段代码只使用了几个额外的变量(left, right, start, mid),它们使用的空间是常数级别的,与输入数组的大小无关。
- 因此,空间复杂度是 O(1),即常数空间复杂度。
五、总结知识点
1. 二分查找(Binary Search):
- 二分查找是一种在有序数组中查找特定元素的高效算法。
- 它通过不断将搜索区间减半来快速定位元素的位置。
- 在代码中,二分查找被用来寻找旋转数组的旋转点,以及在确定的一侧查找目标值。
2. 循环不变量(Loop Invariant):
- 在二分查找的过程中,循环不变量是指在每个迭代步骤中保持不变的量。
- 在这段代码中,循环不变量是左闭右闭的区间
[left, right]
,表示目标值(或旋转点)可能存在的范围。
3. 边界条件处理:
- 代码中对于边界条件进行了处理,例如当输入数组为空或长度为0时,直接返回
false
。 - 在二分查找的过程中,对于
left
和right
的更新也考虑了边界情况,以避免数组越界。
4. 递归与迭代:
- 虽然这段代码使用的是迭代的方式来实现二分查找,但二分查找也可以用递归的方式来实现。
- 迭代通常在空间复杂度上优于递归,因为它不需要额外的栈空间。
5. 整数除法与取余:
- 在计算中点
mid
时,使用了(right - left) / 2
来避免潜在的整数溢出问题,这是整数除法的一个应用。 - 在 Java 中,整数除法会自动向下取整,所以这里不需要使用取余操作。
6. 逻辑判断与分支:
- 代码中使用了逻辑判断来确定目标值可能在数组的哪一侧,并据此调整搜索区间。
- 这体现了分而治之的思想,将大问题分解为更小的、更容易解决的问题。
7. 算法优化:
- 通过先找到旋转点,将问题转化为在两个有序数组中查找目标值的问题,从而优化了查找过程。
- 这种优化减少了不必要的比较次数,提高了算法的效率。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。