2

给定一个数组，例如[7,8,9,0,1,2,3,4,5,6]，是否可以比 O(n) 更快地确定旋转发生的索引？

使用 O(n)，只需遍历所有元素并将第一个递减元素标记为索引。

一个可能更好的解决方案是从两端向中间迭代，但这仍然是 O(n) 的最坏情况。

4

6 回答 6

3

（编辑：下面假设元素是不同的。如果它们不不同，我认为没有什么比扫描数组更好的了。）

你可以对它进行二分搜索。我不会发布任何代码，但这是一般的想法：（我将假设a >= b其余部分。如果a < b，那么我们知道它仍然处于排序顺序）

取第一个元素，调用它a，最后一个元素b，和中间元素，调用它c。

如果a < c，那么您知道枢轴在c和之间b，并且您可以递归（将c和b作为您的新端点）。如果a > c，那么您知道枢轴位于两者之间的某个位置，并在这一半（以a和c作为结束）中递归。

附录：为了扩展到具有重复的情况，如果我们有，那么我们以and作为我们的结束a = c > b进行递归，而如果，我们从to扫描以查看是否存在某些元素使其不同。如果它不存在，那么 and 之间的所有数字都是相等的，因此我们以and作为我们的目的进行递归。如果是这样，有两种情况：cba = c = bacdaccb

a > d < b: 这里，d是我们从左边扫描以来最小的元素，我们就完成了。: 在这里，我们知道答案在和
a < d > b之间，因此我们以它们为目的进行递归。db

在最好的情况下，我们永远不必使用相等的情况，给我们O(log n). 最坏的情况是，这些扫描几乎涵盖了所有阵列，给了我们O(n).

于 2012-08-07T23:52:42.273 回答
2

对于 N 大小的数组，如果该数组已旋转至少 1 次且少于 N 次，我认为它会正常工作：

int low=0, high = n-1;
int mid = (low +high)/2;
while( mid != low && mid != high)
 {
  if(a[low] < a[mid])
  low = mid;
  else
  high = mid;
  mid = (low + high)/2;
 }
return high;
于 2013-03-21T09:39:53.633 回答
1

您可以使用二进制搜索。如果您选择 1 作为中心值，则您知道休息时间在上半场，因为 7 > 1 < 6。

于 2012-08-07T23:51:29.277 回答
0

一种观察是移位等于最小元素的索引。因此，您所要做的就是使用二进制搜索来找到最小元素。唯一的问题是，如果数组具有相等的元素，则任务会变得有点棘手：您无法获得比O(N)时间更好的大 O 效率，因为您可以在输入[0, 0, 0, 0, ..., 100, 0, 0, 0, ..., 0]中找到比线性更快的唯一非零元素当然。但是下面的算法仍然实现了O(Mins + Log(N))whereMins是最小元素的数量，如果它array[0]是最小值之一（否则Mins = 0不给予惩罚）。

l = 0;
r = len(array) - 1;
while( l < r && array[l] == array[r] ) {
    l = l + 1;
}

while( l < r ) {
    m = (l + r) / 2;
    if( array[m] > array[r] ) {
        l = m + 1;
    } else {
        r = m;
    }
}

// Here l is the answer: shifting the array l elements left will make it sorted

这适用于O(log N)唯一元素数组和O(N)非唯一元素数组（但仍然比大多数输入的简单解决方案更快）。

于 2012-08-07T23:54:43.230 回答
0

前提

  • 数组按升序排序
  • 数组左旋转

方法

  • 首先我们需要找到最小元素所在的索引。
  • 数组旋转的次数将等于数组长度与最小元素所在索引的差值。

所以任务是找到最小元素的索引。我们可以通过两种方式找到最低元素的索引

方法1 -

  • 只需遍历数组，当当前元素小于下一个元素时，当前索引就是最小元素的索引。在最坏的情况下，这将需要 O(n)

方法二

  • 使用 (lowIndex+highIndex)/2 找到中间元素
  • 然后我们需要找到中间元素的哪一侧可以找到最小的元素，因为它可以在中间元素的左侧或右侧找到
  • 我们将第一个元素与中间元素进行比较，如果第一个元素大于中间元素，则表示最小元素位于中间元素的左侧，并且
  • 如果第一个元素小于中间元素，则可以在中间元素的右侧找到最低元素

所以这可以像二进制搜索一样应用，并且在 O(log(n)) 中我们可以找到最小元素的索引

于 2016-09-02T18:17:15.333 回答
0

使用递归方法：

static void Main(string[] args) { var arr = new int[]{7,8,9,0,1,2,3,4,5,6}; Console.WriteLine(FindRotation(arr)); }

    private static int FindRotation(int[] arr)
    {
        var mid = arr.Length / 2;
        return CheckRotation(arr, 0, mid, arr.Length-1);
    }

    private static int CheckRotation(int[] arr, int start, int mid, int end)
    {
        var returnVal = 0;
        if (start < end && end - start > 1)
        {
            if (arr[start] > arr[mid])
            {
                returnVal = CheckRotation(arr, start, start + ((mid - start) / 2), mid);
            }
            else if (arr[end] < arr[mid])
            {
                returnVal = CheckRotation(arr, mid, mid + ((end - mid) / 2), end);
            }
        }
        else
        {
            returnVal = end;
        }

        return returnVal;
    }
于 2017-09-11T22:31:15.340 回答