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.

思路

递增数组被移动了，找出最小的元素，数组中无重复的元素。

1. 调用STL，sort快排然后取第一个元素。

2. 某个数的后一个比他小，那么后一个就是最小的。如果一直是递增的，那么第一个就是最小的。

代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[0];
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        int i;
        if (nums.size() == 1)
            return nums[0];
        for (i = 0; i < nums.size(); i++)
        {
            if (nums[i + 1] > nums[i])
            {
                if (i + 1 == nums.size() - 1)
                {
                    return nums[0];
                }
            }
            else
                return nums[i + 1];
        }
    }
};