学习用品

旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M

只是空行用

题目分析

我看到提交的答案里好多用二分查找什么的,但是依照题意,我们不是只需要遍历一边序列,找到第一个比前面的数小的数就可以了吗?比如示例序列中,1是第一个比5小的,由于原先的输入序列是非递减的,所以1是最小的。这样可以获得O(n)的时间复杂度,不香吗?

只是空行用

代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        for(int i = 0; i < rotateArray.size(); i++)
        {
            if(rotateArray[i + 1] < rotateArray[i])
                return rotateArray[i + 1];
        }
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注