一、题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,4] - 若旋转
7次，则可以得到[0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例 1：
输入：nums = [1,3,5] 输出：1
示例 2：
输入：nums = [2,2,2,0,1] 输出：0
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums原来是一个升序排序的数组，并进行了1至n次旋转
二、解题思路
要解决这个问题，我们可以使用二分查找的变种。由于数组最初是排序的，旋转之后，数组被分为两部分，每部分都是有序的。我们的任务是找到这两部分之间的边界，即找到最小值。
解题思路如下：
1. 初始化两个指针，left指向数组的起始位置，right指向数组的末尾位置。
2. 当left < right时，进行循环：
- 计算中间位置
mid。 - 如果
nums[mid] > nums[right]，说明最小值一定在mid的右侧，因此我们将left设置为mid + 1。 - 如果
nums[mid] < nums[right]，说明mid可能是最小值，或者最小值在mid的左侧，我们将right设置为mid。 - 如果
nums[mid] == nums[right]，我们无法确定最小值是在左侧还是右侧，但我们可以缩小查找范围，将right减一。
3. 当循环结束时，left和right指向同一个位置，该位置即为最小值所在的位置。
三、具体代码
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
// 当nums[mid]和nums[right]相等时，无法判断最小值是在左侧还是右侧
// 此时可以将right左移一位，缩小查找范围
right--;
}
}
// 循环结束时，left和right指向同一个位置，该位置即为最小值所在的位置
return nums[left];
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 我们使用的是二分查找的方法，每次迭代都会将搜索区间减半。
- 在最坏的情况下，每次迭代都会将搜索区间的大小减少一个元素，直到找到最小元素或者搜索区间为空。
- 假设数组的长度为n，那么最多需要执行log2(n)次迭代，因为每次迭代都会将搜索区间减半。
- 因此，时间复杂度为O(log n)，其中n是数组的长度。
2. 空间复杂度
- 我们在这个算法中只使用了几个变量来存储索引值（left, right, mid），不管输入数组的大小如何，这些变量所占用的空间都是固定的。
- 我们没有使用额外的数据结构来存储数组中的元素或者数组的副本。
- 因此，空间复杂度为O(1)，即常数空间复杂度。
综上所述，这个算法的时间复杂度是O(log n)，空间复杂度是O(1)。
五、总结知识点
二分查找算法：这是一种在有序数组中查找特定元素的搜索算法，通过将数组分为两半来减少搜索空间，从而提高搜索效率。
循环条件：使用
while (left < right)作为循环条件，确保循环在left和right指针相遇时结束。计算中点：使用
int mid = left + (right - left) / 2;来计算中点，避免直接使用(left + right) / 2可能导致的整数溢出问题。比较和赋值操作：通过比较
nums[mid]和nums[right]的值来决定是向左查找还是向右查找，或者是在无法确定最小值位置时将right左移一位。边界条件处理：当
nums[mid]和nums[right]相等时，无法确定最小值是在左侧还是右侧，此时通过将right--来缩小查找范围，这是一种处理重复元素的策略。返回最小值：当循环结束时，
left和right指向同一个位置，该位置的值即为数组中的最小值。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
