刷题平台

题目描述

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

题目分析

非递减：说明输入的数组不是递增的就是含有多个相等的元素构成。

递增排序情况：

由于输入的是一个旋转数组，意味着原始数组前较小的元素移动到数组末尾，因此可以确定旋转后的数组第一个元素一定是大于最后一个元素的。如果不满足这个条件，则说明不是旋转数组。（这可以作为判断数组是否旋转的条件）

查找数组中的最小元素：这个可以根据数据结构中的查找选择合适的方法。由于数组是递增排序的，因此数组可以看成在有序表中进行查找。

有序表中查找的方法：二分查找，插值查找，斐波那契查找。三种方法的时间复杂度都是O[logn]

二分法：

优点：对于静态的查找表进行查找，这种算法比较好

缺点：对于频繁插入删除的顺序表来说，这种算法就不建议使用

插值查找：

优点：对于顺序表较长，且表中的元素大小分布均匀（元素值之间相差较小），较二分法要好。

缺点：当数组中的元素大小分布不均匀时（例如{1，2，9999，99999}），这种算法效率就比较差。

斐波那契查找：

优点：这种算法在查找过程中仅仅进行最简单的加减法运算，在大量数据下查找，会占有优势。

缺点：虽然这种算法的平均查找性能优于二分法，但是如果查找的关键字位于较长的半区，则查找效率要低于二分法。

通过分析得知：旋转数组是一个静态数组，但是数组中的元素大小分布不确定，最小元素的位置也不确定，因此选择二分查找法是不错的选择。

旋转数组可以看成两个递增序列。
取两个指针分别指向第一个元素和最后一个元素。
在数组中取中间元素作为比较对象，若中间值大于第一个元素，则说明中间值在前面一个递增序列中，将第一个指针指向中间元素；

若中间值小于最后一个元素，则说明中间值在后面一个递增序列中，则将第二个指针指向中间元素。

循环以上步骤。

当两个指针指向相邻元素时，右指针指向的元素就是最小值。

含有多个相等元素：

由于含有多个相等元素，可能造成取得中间元素可能与第一个元素相等或与最后一个元素相等，即不能判断所取得中间元素是属于前一个递增序列还是后一个递增序列。

此时就要通过使用顺序查找的方法，寻找最小值。

以下是代码：

class Solution
{
public:
    int minNumberInRotateArray(vector<int>rotateArray)
    {
        int size = rotateArray.size();
        if (size == 0)
        {
            return 0;
        }
        int left = 0, mid = 0, right = size - 1;
        while(rotateArray[left] >= rotateArray[right]) // 旋转数组的判断
        {
            if (right - left == 1)   // 左右指针指向相邻元素
            {
                mid = right;    // 指向右面的指针的元素为最小值
                break;
            }
            mid = left + (right - left)/2;
            if (rotateArray[left] == rotateArray[right] && rotateArray[mid] == rotateArray[left]) // 当取的中间值与左右指针指向的元素相等
            {
                return minNum(rotateArray, left, right); // 顺序查找
            }
            if (rotateArray[mid] >= rotateArray[left])
                left = mid;
            else
                right = mid;
        }
        return rotateArray[mid];
    }
private:
    int minNum(vector<int>num, int left, int right)
    {
        int result = num[left];
        for (int i = left + 1; i < right; i++) // 只需遍历除去第一个和最后一个的中间数组
        {
            if (result > num[i])
            {
                result = num[i];
            }
        }
        return result;
    }
};

参考博文链接：https://cuijiahua.com/blog/2017/11/basis_6.html

zerofly's Blog

求旋转数组最小值(C++版)

刷题平台

题目描述

题目分析