我最近遇到了一个编程问题,如下:
给出一个排序数组,并在某个未知点旋转数组,我必须在其中找到最小元素 . 数组也可以包含重复项 .
例如:
Input: {5, 6, 1, 2, 3, 4}
Output: 1
Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2}
Output: 0
我遵循的简单解决方案是遍历整个数组并找到最小值 . 这个解决方案需要时间O(n) . 我理解最小元素是前一个元素大于它的事实 . 如果不存在这样的元素,则没有旋转,并且第一元素将是最小的 .
但我被要求提供O(Logn)解决方案 . 有没有办法在O(Logn)时间内解决它?
3 回答
脱离我的头顶:
注意第一个条目
执行二分查找;如果枢轴元件大于或等于存储的第一元件,则在每个阶段选择右半部分;如果枢轴元件较小,则选择左半部分 .
例如,给定
{4,5,6,7,1,2,3}
:转轴
7
>4
,减少到右半{1,2,3}
转轴
2
<4
,减少到左半1
.只考虑一个元素,答案是
1
.看到这个:因为它是排序数组 . 我需要应用二进制搜索来查找枢轴..
最低元素将是数组被旋转的位置 .
叫这个
findpivot(arr,0,n-1);
迭代方法: