旋转整数数组的递归方法分析

Question

在LeetCode上解决数组旋转时，我编写了一个递归算法来解决这个问题：

给定一个数组，将数组向右旋转k步，其中k为非负。

例1：

输入： Nums=[1,2,3,4,5,6,7]， k=3输出：[5,6,7,1,2,3,4]说明：向右旋转1步：[7,1,2,3,4,5,6]向右旋转2步：[6,7,1,2,3,4,5]旋转3步向右：[5,6,7,1,2,3,4]

例2：

输入：nums=[-1，-100,3,99]，k=2输出：[3,99，-1，-100]说明：向右旋转1步：[99，-1，-100,3]向右旋转2步：[3,99，-1，-100]

约束：

1.

为了进一步澄清，这里是问题的链接。

我提出的解决方案如下：

class Solution {
  public void rotate(int[] nums, int k) {
    rotateArr(nums, nums.length, k % nums.length, 0);
  }

  public static void rotateArr(int[] arr, int len, int steps, int current) {
    if (len <= steps) {
      return;
    }
    rotateArr(arr, len - 1, steps, current + 1);
    int stepsTaken = 0;
    int i = current;
    int temp;
    while (stepsTaken < steps) {
      temp = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
      i++;
      stepsTaken++;
    }
  }
}

根据我对解的分析，函数RotateArr（）将首先除以nums.length-k倍。在那之后，它开始征服，这将发生在nums.length-k 1步，在每一步它执行k操作。总结我们得到的一切：

• （nums.length-k）（nums.length-k 1）k=nums.lengthnums.lengthk-k^2

虽然我有一个二次项，但它是一个常数，因此我相信我的运行时是O（n）。
我想知道以下内容：

• 我的分析正确吗

Answer 1

Utkarsh Tiwari，我认为你的分析是不正确的。根据我的计算，征服步骤将发生在A.长度-k次，而不是A.长度-k 1。

让我们考虑一下你提到的第二个输入数组：

[-1, -100, 3, 99]

这里，对rotatarray（A，4，2，0）的第一个调用发生在main（）方法中。第二个递归调用是：rotatarray（A，3，2，1），最后一个是：rotatarray（A，2，2）。

但是，在最后一次递归调用中，由于基本条件得到满足，所以征服不会发生。

if(length <= steps) return.

该函数将简单地返回最后一次，而不执行任何重要步骤。因此，所有的k操作数量将只发生在前两个递归调用中，这是根据表达式A.长度-k或4-2在这种情况下。

因此，时间复杂度将是（A.长-k）*k。

现在，让我们看看您提供的约束：

1

-2^31

0

这里，k不是常数。它的可能值甚至超过了nums.length的最大值。时间复杂度取决于A. long和k的值。如果k的可能值在5到20之间，它将是O（nums.length）。但是，在当前约束条件下，它可以接受一个超过A. long的值。

让我们注意一下实现中的另一个微妙细节。在对rotatarray（）的第一次调用中，您将k%A.length作为参数之一传递。现在，k的可能值降低为：

0 <= k < A.length

如果我们选择k的值作为A.长度/2，并输入时间复杂度，我们得到：

(A.length - A.length/2) * A.length

这将减少到O（A.length^2），这将是最糟糕的情况复杂性。

我希望我帮助过你。如果在解决方案中遇到任何问题，请发表评论。