LeetCode 153. Find Minimum in Rotated Sorted Array （在旋轉有序數組中找到最小值）

Suppose an array sorted in ascending order 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.

You may assume no duplicate exists in the array.

題目標簽：Array, Binary Search

　　題目給了我們一個旋轉有序數組，讓我們找到最小值。如果是在還沒有旋轉的情況下，那么我們知道，最小值就是第一個數字。

　　那么當遇到旋轉的情況呢，我們就需要找到那個 “斷點” 的兩個數字，換句話說，就是最大值和最小值，而且這兩個數字一定是相鄰的。

　　我們來看一下例子：

　　0 ?1 ?2 ?4 ?5 ?6 ?7　　直接返回第一個數字

　　1 ?2 ?4 ?5 ?6 ?7 ?0　　返回7 和0 中小的那個數字

　　2 ?4 ?5 ?6 ?7 ?0 ?1　　

　　4 ?5 ?6 ?7 ?0 ?1 ?2

　　5 ?6 ?7 ?0 ?1 ?2 ?4

　　6 ?7 ?0 ?1 ?2 ?4 ?5

　　7 ?0 ?1 ?2 ?4 ?5 ?6

　　利用二分法來找到最大和最小的兩個數字。

　　rule 1：如果 mid 小于 left，意味著最大的數字在左邊，繼續去左邊找，把right = mid，這里要包括mid，因為mid 可能是最小的數字；

　　rule 2：如果 mid 大于 right，意味著最小的數字在右邊，繼續去右邊找，把left = mid，這里要包括mid，因為mid 可能是最大的數字。

　　當left 和right 相鄰的時候，返回小的數字就可以了。

Java Solution:

Runtime beats 53.07%?

完成日期：08/30/2017

關鍵詞：Array， Binary search

關鍵點：旋轉中，min 和 max 必然是相鄰的，利用二分法找到min 和max

 1 class Solution 
 2 {
 3     public int findMin(int[] nums) 
 4     {
 5         if(nums.length == 1)
 6             return nums[0];
 7         
 8         int left = 0;
 9         int right = nums.length - 1;
10         
11         if(nums[left] < nums[right])
12             return nums[0];
13         
14         while(left + 1 != right)
15         {
16             int mid = left + (right - left) / 2;
17             
18             if(nums[mid] < nums[left]) // if left is greater than mid, move to left
19                 right = mid;
20             else if(nums[mid] > nums[right]) // if mid one is greater than right, move to right
21                 left = mid;
22         }
23         
24         // if there are only two number
25         return Math.min(nums[left], nums[right]);
26     }
27 }

參考資料：N/A

LeetCode 算法題目列表 -?LeetCode Algorithms Questions List

轉載于:https://www.cnblogs.com/jimmycheng/p/7456345.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/253579.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/253579.shtml
英文地址，請注明出處：http://en.pswp.cn/news/253579.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！