首页 > 代码库 > LeetCode 新题: Find Minimum in Rotated Sorted Array 解题报告-二分法模板解法
LeetCode 新题: Find Minimum in Rotated Sorted Array 解题报告-二分法模板解法
Find Minimum in Rotated Sorted Array
Question Solution
Suppose a sorted array is rotated at some pivot unknown to youbeforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
解答1：
这个题目trick的地方在于，它的旋转pivot次数未知。所以有可能它转了一圈又转回了原处
所以我们代码要处理2种情况：
我们还是用二分法来做。比起全部扫一次，二分法可以做到LogN的复杂度。
1. Sorted
这种情况简单，先计算出mid的值，如果它处在左右的中间，证明这个数列是正常的sorted,直接返回左边。
2. 中间断开（也就是说旋转过）
我们的目的是要找出存在断口的地方。所以我们可以每次求一下mid的值，把mid跟左边比一下，如果是正常序，就丢掉左边，反之丢掉右边，不断反复直到找到断口。
分析一下：
比如4 5 6 7 0 1 2 从中间断开后，它是由一个有序跟一个无序的序列组成的。
如果left = 0, right = 6,mid = 3, 那么4， 5， 6， 7 是正序， 7， 0， 1，2是逆序，所以我们要丢掉左边。这样反复操作，直到数列中只有2个数字，就是断开处，这题我们会得到7，0，返回后一个就可以了。
以下图示简单描述了通过三步操作逐步逼近断口处。每一次我们可以扔掉一半，速度是LogN.
注意，丢掉半边时，mid不可以丢掉，因为有可能mid就是答案。
例子： 3， 1， 2 的时候，3， 1是逆序，1， 2是正序，如果你扔掉1，2你就丢掉了答案。
我们的目的是要找出存在断口的地方。所以我们可以每次求一下mid的值，把mid跟左边比一下，如果是正常序，就丢掉左边，反之丢掉右边，不断反复直到找到断口。
分析一下：
比如4 5 6 7 0 1 2 从中间断开后，它是由一个有序跟一个无序的序列组成的。
如果left = 0, right = 6,mid = 3, 那么4， 5， 6， 7 是正序， 7， 0， 1，2是逆序，所以我们要丢掉左边。这样反复操作，直到数列中只有2个数字，就是断开处，这题我们会得到7，0，返回后一个就可以了。
以下图示简单描述了通过三步操作逐步逼近断口处。每一次我们可以扔掉一半，速度是LogN.
注意，丢掉半边时，mid不可以丢掉，因为有可能mid就是答案。
例子： 3， 1， 2 的时候，3， 1是逆序，1， 2是正序，如果你扔掉1，2你就丢掉了答案。
1 // Solution 1: 2 public int findMin1(int[] num) { 3 if (num == null || num.length == 0) { 4 return 0; 5 } 6 7 if (num.length == 1) { 8 return num[0]; 9 }10 11 12 // 至少有2个元素，才有讨论的价值 13 int l = 0;14 int r = num.length - 1;15 16 while (l < r) {17 int mid = l + (r - l)/2;18 // Means that there is no rotate.19 if (num[mid] >= num[l] && num[mid] <= num[r]) {20 return num[0];21 }22 23 // rotate > 0的情况 24 if (l == r - 1) {25 // 当只余下2个元素的时候,这里是断点，右边的是小值26 return num[r];27 }28 29 if (num[mid] >= num[l]) {30 // The left side is sorted. Discard left.31 l = mid;32 } else {33 // The right side is sorted.34 r = mid;35 }36 }37 38 return 0;39 }
解答2：
采用九章算法的二分法模板来解：
采用九章算法的二分法模板来解：
这个模板最大的好处是 while(left < right - 1) 这样的话，终止时就一定是left = right - 1，而且mid 一直会是在中间，不会靠到left去。判断起来会相当
便利。
1 // solution 2: 2 public int findMin(int[] A) { 3 if (A == null || A.length == 0) { 4 return 0; 5 } 6 7 if (A.length == 1) { 8 return A[0]; 9 } else if (A.length == 2) {10 return Math.min(A[0], A[1]);11 }12 13 // 至少有3个元素，才有讨论的价值 14 int l = 0;15 int r = A.length - 1;16 17 while (l < r - 1) {18 int m = l + (r - l) / 2;19 20 // means that there is no rotate.21 if (A[m] < A[r] && A[m] > A[l]) {22 return A[0];23 }24 25 // left side is sorted.26 if (A[m] > A[l]) {27 l = m;28 } else {29 r = m;30 }31 }32 33 return A[r];34 }
所以以后一定要多使用模板化的编程 ，特别是这里总结的二分法模板:
1 while (l < r - 1) { 2 int m = l + (r - l) / 2; 3 4 // means that there is no rotate. 5 ... 这里添加各种退出条件，比如找到了目标值等 8 9 // left side is sorted.10 if (A[m] > A[l]) {11 l = m;12 } else {13 r = m;14 }15 }
GitHub：
GitHub代码链接LeetCode 新题: Find Minimum in Rotated Sorted Array 解题报告-二分法模板解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。