题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

初始代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {

    }
};

解法1

好不夸张的说, 一开始看到这个题, 一直没想明白这个非递减有个什么用. 非递减的对立面是递减, 也就是说, 形如{9, 5, 4, 2, 1}这般的数组, 而只要不是这样的数组, 都可以称之为非递减, 即数组{2, 5, 3, 6, 1, 7}也可称为非递减. 所以, 这不就是普普通通的随机数组吗? 搞不懂题目为什么要把这作为一个条件特别提出来.

既然是随机数组, 也没什么算法好讲. 只能用暴力求解硬刚咯.

就是一个简单的O(n)复杂度的求数组最小值的遍历操作, 俗称为"打擂算法". 遍历过程中, 碰到的已知的最小元素就可以坐上"擂主"的宝座, 但保不准下一次比较时这个"擂主"就被PK下来了.

下面是代码实现:

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

        return min;
    }
};

解法2

要么是出这个题的人没脑子, 要么就是我自己还没有完全理解题意. 通过查看其它题解, 算是理解题干中的"非递减排序数组的一个旋转"意味着什么了.
即, 首先有一个数组, 它已经排好序了, 而且是按照非递减的顺序进行排序的(虽然我更倾向于将这类序列说成是非单调递增序列). 然后, 这个排好序的数组被做了一次旋转操作后, 才作为函数的参数被传进来.

弄清楚这一点, 就好说了, 因为这个数组还是挺特殊的.

如果采用二分法来查找该数组中的最小元素的话, 首先我们会取到数组的中间元素或者说中间元素的下标, 记为mid. 然后我们要拿mid处的元素和另一个元素进行比较, 根据比较的结果来确定下一步是在左半边数组里接着找, 还是在右半边数组里接着找.
这个另一个元素我们可以取当前数组的最右侧元素.
来做一次模拟就清楚了:

• 如果当前mid位置元素大于最右端的元素, 比方说当前数组为{3, 4, 1, 2}, mid处元素为4, 最右边元素为2, 4 > 2. 根据旋转前的数组的非递减特性, 可以判断最小数字在mid右侧.

  注意: 当数组元素个数为偶数时, 我们取最中间两个下标的较小的那一个为mid, 取较大的那一个当然也是可行的, 倒是取较大的一个作为mid后其它地方和取较小的那个为mid有没有区别, 需不需要微调, 则需要另外考虑一下了, 后面开一小节来讨论.

• 如果当前mid位置元素小于等于最右端元素, 比方说当前数组为{4, 1, 2, 3}或者{4, 1, 2, 2, 2}, 同样根据旋转前数组的非递减特性, 可以判断最小数字在mid的左侧(包括mid在内).

由上面的思路, 可以实现二分法查找最小元素的算法了, 如下:

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

        int mid = (rotateArray.size() - 1) / 2;
        if(rotateArray.at(mid) > rotateArray.at(rotateArray.size() - 1))
        {
            vector<int> tmp(rotateArray.begin()+mid+1, rotateArray.end());
            return minNumberInRotateArray(tmp);
        }
        else
        {
            vector<int> tmp(rotateArray.begin(), rotateArray.begin()+mid+1);
            return minNumberInRotateArray(tmp);
        }
    }
};

关于数组长度为偶数时, mid取值的问题

上面的解法2, mid在数组长度为偶数时, 取的是中间两个下标的较小者. 如果取较大者为mid会如何呢?

同样先以{3, 4, 1, 2}为例, 现在mid处的元素值为1, 数组最右端元素为2, 1 < 2, 因此, 按照上面的思路, 应该认为最小数字应该从mid左边的数组元素中去找(包括mid位置的元素), 而实际上也正是如此.

随后以{2, 3, 4, 1}为例, 现在mid处元素值为4, 大于数组最右端元素1, 按照上面的思路, 接下来应该从mid右边的数组元素中找最小数字, 而实际上这也是没错的.

是否可以就此下结论说: 在数组长度为偶数时, mid无论是取中间两个下标的任何一个值, 对后续的操作都是没有影响的, 可以使用同一套代码了呢?

修改后使用自测数据{3, 4, 5, 1, 2}测了一遍, 出现了内存超限的问题. 心算了一下, 在数组只含有{1, 2}两个元素的时候, 如果按上面的算法, 2 <= 2, 因此下一步从mid所处位置元素左边继续找(包括mid处元素在内), 会发现, 下一步的数组还是{1, 2}, 就这样, 陷入死循环退不出了...

要避免这种死循环的出现, 可以在函数开头添加一个对数组长度为2时的判断: 当数组只有两个元素时, 直接返回其中的较小值即可.

下面时通过的代码:

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

        int mid = rotateArray.size() / 2;
        if(rotateArray.at(mid) > rotateArray.at(rotateArray.size() - 1))
        {
            vector<int> tmp(rotateArray.begin()+mid+1, rotateArray.end());
            return minNumberInRotateArray(tmp);
        }
        else
        {
            vector<int> tmp(rotateArray.begin(), rotateArray.begin()+mid+1);
            return minNumberInRotateArray(tmp);
        }
    }
};