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

Question

在LeetCode上解决Array rotation的时候，写了一个递归算法来解决这个问题：

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 2*104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

为了进一步说明问题 link 是 here.

我想出的解决方案如下：

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.length + nums.length k - k^2

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

我的分析正确吗？
如果它是正确的，那为什么我在 LeetCode 上的运行时间总是在 100 毫秒左右？与其他 0 毫秒相反。是因为递归吗？

Answer 1

Utkarsh Tiwari，我认为您的分析不正确。根据我的计算，征服步骤将发生 A.length - k 次并且不会 A.length - k + 1.

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

[-1, -100, 3, 99]

这里第一次调用rotateArray(A, 4, 2, 0)发生在main()方法中。第二个递归调用是这样的：rotateArray(A, 3, 2, 1) 最后一个是这样的：rotateArray(A, 2, 2, 2).

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

if(length <= steps) return.

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

因此，time complexity 将是 (A.length-k) * k。

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

1 <= nums.length <= 2 * 10^4

-2^31 <= nums[i] <= 2^31 - 1

0 <= k <= 10^5

在这里，k 是 而不是 常数。它的可能值甚至超过了nums.length的最大值。 time complexity 取决于 both 取决于 A.length 和 k 的值。 如果 k 的可能值介于 5 到 20 之间，则应该是 O(nums.length)。但是，在当前限制条件下，它可以取一个大于 A.length 的值。

让我们注意您的实施中的另一个细微细节。在对 rotateArray() 的第一次调用中，您将 k % A.length 作为参数之一传递。现在 k 的可能值减少为：

0 <= k < A.length

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

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

减少到 O(A.length^2)，这将是 worst case complexity。

希望对您有所帮助。 如果您在解决方案中遇到任何问题，请发表评论。

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

Analysis of recursive approach for rotating an array of integers

java

arrays

recursion

time-complexity