154. Find Minimum in Rotated Sorted Array II
题目描述和难度
- 题目描述：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5] 输出: 1
示例 2：
输入: [2,2,2,0,1] 输出: 0
说明：
- 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
- 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
- 题目难度：困难。
- 英文网址：154. Find Minimum in Rotated Sorted Array II 。
- 中文网址：154. 寻找旋转排序数组中的最小值 II 。
思路分析
求解关键：使用分治思想的，这道题和 LeetCode 第 153 题没有区别。
参考解答
参考解答1：使用分治的思想。
public class Solution {
public int findMin(int[] nums) {
int len = nums.length;
if (len == 0) {
throw new IllegalArgumentException("数组为空，最小值不存在");
}
return findMin(nums, 0, len - 1);
}
private int findMin(int[] nums, int left, int right) {
if (left + 1 >= right) {
return Math.min(nums[left], nums[right]);
}
if (nums[left] < nums[right]) {
return nums[left];
}
int mid = left + (right - left) / 2;
return Math.min(findMin(nums, left, mid - 1), findMin(nums, mid, right));
}
public static void main(String[] args) {
int[] nums = {1, 3, 5};
Solution solution = new Solution();
int solutionMin = solution.findMin(nums);
System.out.println(solutionMin);
}
}
本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0154-find-minimum-in-rotated-sorted-array-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。