LeetCode 154 Find Minimum in Rotated Sorted Array II (二分 或 分治)

本文主要是介绍LeetCode 154 Find Minimum in Rotated Sorted Array II (二分 或 分治)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

题目链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

题目分析：和Find Minimum in Rotated Sorted Array比就是多了元素可重复的条件，在原来基础上改

public class Solution {public int findMin(int[] nums) {int l = 0, r = nums.length - 1, mid;while (l < r) {mid = (l + r) >> 1;if (nums[mid] == nums[r]) {r --;}else if (nums[mid] > nums[r]) {l = mid + 1;}else {r = mid;}}return nums[l];}
}

其实就是找最小值。。。直接分治，也是logn的复杂度

public class Solution {int DFS (int[] nums, int l, int r) {if (l == r) {return nums[l];}if (l == r - 1) {return Math.min(nums[l], nums[r]);}int mid = (l + r) >> 1;return Math.min(DFS(nums, l, mid), DFS(nums, mid + 1, r));}public int findMin(int[] nums) {return DFS(nums, 0, nums.length - 1);}
}

这篇关于LeetCode 154 Find Minimum in Rotated Sorted Array II (二分 或 分治)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---