已排序但旋转的数组

Question

给定一个已排序但旋转的数组,您如何找到枢轴？我在接受采访时被问到这个问题.什么是旋转阵列？

我在互联网上得到了这个,但它根本不清楚.

在旋转的有序数组中,只能保证对A和B中的一个进行排序.

枢轴是左元素和右元素中较小的元素.

Answer 1

我认为一个有序的旋转数组是这样的:

排序方式:

2, 7, 32, 48, 55

旋转:

 32, 48, 55, 2, 7

2是枢轴.您需要找到枢轴的位置.

解决方案应该很简单:枢轴是排序结束并重新开始的点.这也是你"在互联网上找到的":

(假设数组按升序排序.如果按降序排列,则更<改为>)

for (i = 0; i<array.length; i++)
{
    if array[i+1] < array[i]
        return i + 1;
        break;
}

补充:我可以很快想到的分而治之的逻辑.只要第一个元素大于最后一个元素,就继续拆分数组.如果split(sub)数组的第一个元素不大于最后一个元素,则第一个元素是原始数组的pivot.

int left = 0;
int right = array.length - 1;
while (array[left] > array[right])
{
    int mid = left + (left + right) / 2;
    if(array[mid] > array[right])
    {
        left = mid + 1;
    }
    else
    {
        right = mid;
    }
}
return left;

顺便说一句,如果你在一次采访中被问到这个问题,而你不知道排序的旋转阵列是什么,你可以问.如果面试官向你解释然后你给他们一个解决方案,你应该是好的.我个人不在乎是否有人不懂术语.只要他们能够思考,找到逻辑和代码,它应该没问题.