很自然地,最直观的解法就是设置一个最小值,并顺次检查数组的每一个元素,如果小于最小值,就更新这个值。最后将它输出即可。
最容易想到的往往都不是最优的解法。这种算法的时间复杂度为O(n),没有利用这是一个已排序数组的旋转这个特性。代码从略。
一般我们对一个已排序数组进行查找较好的方法是二分法。所以我们试着用来解这道题。
假设这个数组有n个元素,则它可以分为有旋转和无旋转两种情况(旋转n次也相当于无旋转)。当有旋转时,我们将数组分成左右两部分,他们都是递增的子数组,而最小元素是右子数组的第一个元素,因此可以在两部分里面分别用二分法来查找。而无旋转就相当于有旋转的一个特例(一个子数组为空),所以也可依照此法来解。下面是参考思路:
设数组为arr,其左右元素的下标分别是left和right,我们求得其中间元素的下标mid=left+(right-left)/2;如果arr[mid]>arr[mid],表明mid在左子数组中,此时令left=mid。否则表明mid在右子数组中,令right=mid。继续循环即可。
int Min(vector<int> arr)
{
int left=0,right=arr.size()-1;
int mid;
if(arr[left]<arr[right])
return left;
while(left<right-1)
{
if(right-left==1)
{
mid=right;
break;
}
mid=left+(right-left)/2;
if(arr[mid]==arr[left] && arr[mid]==arr[right])
return arr[mid];
if(arr[mid]<=arr[right])
right=mid;
else if(arr[mid]>=arr[left])
left=mid;
}
return arr[mid];
}
然而,当数组为{1,0,1,1,1}时,使用上述算法是无法找出最小元素的。因为刚开始left=0,right=4,mid=2,此时arr[left]=arr[mid]==arr[right],算法就直接返回1,而数组真正最小的元素是0。所以需要加一个判断条件,如果左中右的值相等时,则需要顺序查找。
int MinInOrder(vector<int> arr)
{
if(arr.size()<=0)
return -1;
int min=0;
int i;
for(i=0;i<arr.size();++i)
{
if(arr[i]<arr[min])
min=i;
}
return arr[min];
}
然后将
if(arr[mid]==arr[left] && arr[mid]==arr[right])
return arr[mid];
````
改为
````
if(arr[mid]==arr[left] && arr[mid]==arr[right])
return MinInOrder(arr);
即可。
以上
如果你有任何想法或是可以改进的地方,欢迎和我交流!
完整代码及测试用例在github上:点我前往