leetcode刷题数组类:数组的旋转

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

方法一:调用系统的排序函数

 方法二:利用旋转数组的性质:分析:数组变成了一个非排序状态移动后的数组变成了两截,这两截内的元素是按序排列的,其中一个区间内的所有元素都比另一个区间的任意元素小, 可以根据尾元素作为区分值,没有移动过的数组也需要考虑在内。

转动数组的性质,这个数组其实可以看成两个排序好的数组,一前一后,一大一小,做二分的时候,二分取到的中点有可能在前区间,也有可能在后区间,可以使用尾元素作为区分值,二分中点对应的值比尾元素小的话那就说明二分中点是在后面的区间,大的话就会是在前面的区间。如果中点在后面的区间,那我们就要移动尾指针,如果是在前面的区间的话,我们就要移动首指针,其实就是逐步逼近后区间首元素的一个过程

原文地址:https://www.cnblogs.com/bingzibing/p/13353257.html