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

 class Solution

 {

     public int findMin(int[] nums)

     {

         if(nums.length == 1)

             return nums[0];

         int left = 0;

         int right = nums.length - 1;

         if(nums[left] < nums[right])

             return nums[0];

         while(left + 1 != right)

         {

             int mid = left + (right - left) / 2;

             if(nums[mid] < nums[left]) // if left is greater than mid, move to left

                 right = mid;

             else if(nums[mid] > nums[right]) // if mid one is greater than right, move to right

                 left = mid;

         }

         // if there are only two number

         return Math.min(nums[left], nums[right]);

     }

 }

参考资料：N/A

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

巴特西

LeetCode 153. Find Minimum in Rotated Sorted Array （在旋转有序数组中找到最小值）

最新文章

热门文章