首页 > 代码库 > 【LeetCode】Find Minimum in Rotated Sorted Array 找到旋转后有序数组中的最小值

【LeetCode】Find Minimum in Rotated Sorted Array 找到旋转后有序数组中的最小值

本文原作者:大便一箩筐

文章原地址:http://www.cnblogs.com/dbylk/p/4032570.html

 

原题:

  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.

  You may assume no duplicate exists in the array.

 

解释:

  假定有一个有序数组事先被旋转到了某一个未知的轴,

  (比如 0 1 2 4 5 6 7 旋转后变为 4 5 6 7 0 1 2),

  找到旋转后数组中的最小值,

  假定数组中不存在重复的数据。

 

思路:

  1. 因为原数组是有序的,所以旋转后的数组的第一个元素必定大于最后一个元素,
  2. 若不满足上述条件,说明数组没有旋转或者旋转轴的位置为0,此时可以直接将第一个元素作为答案返回。
  3. 数组从中间被截断后,原数组中的最小值在数组的后半段被丢弃后仍然是数组中最小值。
  4. 以上述三个条件作为基础,我们可以使用二分法找到数组中的最小元素:

① 使用 head 变量标记二分后数组首元素的位置,tail 标记二分数组的尾元素的位置。

② 若 num[head] > num[tail],则继续执行步骤 ③,否则说明数组满足条件1,此时 num[head] 即为所求的最小数。

③ 使用 med 标记数组最中间的元素位置。

④ 若 num[med] > num[head],说明此时数组的左半段是有序的,则旋转点一定在右半段,因此使 head = med,继续执行步骤 ②。

⑤ 若 num[med] < num[head],说明此时数组的左半段是无序的,则旋转点一定在左半段,因此使 tail = med,继续执行步骤 ②。

⑥ 若 num[med] = num[head],说明此时数组中只有两个或一个元素(数组中不存在重复元素),则旋转点一定是 num[head] 和 num[tail] 中的最小值,所以此时返回它们中的最小值即可。

 

源码:

class Solution {public:    int findMin(vector<int> &num) {        int size = num.size();        if (!size) {            return 0;        }        int head = 0;        int tail = size - 1;        while (head <= tail) {            if (num[head] > num[tail]) {                int med = head + tail >> 1;                if (num[med] > num[head]) {                    head = med;                }                else if (num[med] < num[head]) {                    tail = med;                }                else {                    return num[head] < num[tail] ? num[head] : num[tail];                }            }            else {                return num[head];            }        }        return 0;    }};

 

【LeetCode】Find Minimum in Rotated Sorted Array 找到旋转后有序数组中的最小值