排序，但旋转阵列 [英] Sorted but rotated array

问题描述

由于排序的，但旋转阵列你如何找到了支点？有人问我在一次采访中这个问题。什么是旋转阵列？

我得到这个在互联网上，但它不是明确的。

  

在一个旋转排序后的数组中，只有一个A和B的可保证进行排序。

     

枢轴是一种较小的元素，然后在左元素和右元素为好。

解决方案

我觉得一个排序，旋转阵列是这样的：

排序：

  2，7，32，48，55
 

旋转：

  32，48，55，2，7
 

2 的支点。你需要找到支点的位置。

解决方案应该是简单的： 枢轴是其中分拣结束并再次开始点。这也就是你在互联网上找到：

（假设数组按升序排序如果降序排列，变＆LT; 到＆GT; ）

 为（i = 0; I＆LT; array.length;我++）
{
    如果阵列[1 + 1];数组[我]
        返回I + 1;
        打破;
}
 

添加：分而治之的逻辑，我能很快想到的。保持劈裂阵列，只要第一个元素是比最后元件更大。如果分割（分）阵列的第一个元素不大于最后一个元素时，第一个是原阵列的枢

  INT左= 0;
INT右= array.length  -  1;
而（数组[左]＆GT;数组[右]）
{
    INT中期=左+（左+右）/ 2;
    如果（阵列[MID]＆GT;数组[右]）
    {
        左=中间+ 1;
    }
    其他
    {
        右=中间;
    }
}
返回左;
 

顺便说一句，如果你要问这个问题在接受采访时，你根本不知道什么是排序的旋转阵列，你可以问。如果面试官解释给你，然后你给他们一个解决方案，您应该不错。就个人而言，我不会在意，如果有人不知道的术语。只要他们能想到，找到逻辑和code，应该没事。

Given a sorted but rotated array how do you find the pivot ? I was asked this question in an interview. What is a rotated array ?

I got this on internet but its not clear at all.

In a rotated sorted array, only one of A and B can be guaranteed to be sorted.

Pivot is the element which is lesser then in left element and right element as well.

解决方案

I think a sorted, rotated array is something like this:

Sorted:

2, 7, 32, 48, 55

Rotated:

 32, 48, 55, 2, 7

2 is the pivot. You need to find the position of the pivot.

Solution should be simple: the pivot is the point where the sorting ends and starts again. This is also what you "found on the Internet":

(assuming array is sorted in ascending order. If descending order, change < to >)

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

Added: A divide and conquer logic that I could quickly think of. Keep spliting the array as long as the first element is larger than the last element. If the first element of the split (sub) array is not larger than the last element, the first is the pivot of the original array.

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;

BTW, if you were asked this question in an interview, and you did not know what a sorted rotated array is, you can ask. If the interviewer explain it to you and then you give them a solution, you should be good. Personally I wouldn't care if someone does not know terminology. As long as they can think, find logic and code, it should be fine.

这篇关于排序，但旋转阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！