LeetCode 189. Rotate Array：C#实现超时问题及性能优化咨询

题目描述 #

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

示例1 #

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

我的实现（C#） #

public void Rotate(int[] nums, int k) {
    if (k <= 0)
        return;

    int t = 0;

    for (int i = 0; i < k; i++) {
        t = nums[nums.Length - 1];

        for (int j = nums.Length - 1; j > 0; j--) {
            nums[j] = nums[j - 1];
        }

        nums[0] = t;
    }
}

问题说明 #

上述代码可通过所有常规测试用例，但处理大型数组时会因速度不足触发“Time Limit Exceeded”错误。我想知道当前思路存在什么问题，以及如何优化实现提升速度。

问题分析与优化方案 #

当前思路的核心问题 #

你的实现采用逐次右移1位、循环k次的逻辑，时间复杂度为O(n*k)（n为数组长度）。当n和k都很大时（比如n=10^5，k=105），总操作次数会达到10^10级别，远远超出时间限制，这是超时的根本原因。

优化方案1：先简化k值（基础优化） #

首先可以先对k取模，因为旋转n次相当于没有旋转，所以k = k % n。这一步能减少循环次数，但无法改变时间复杂度的量级，仅作为基础优化：

public void Rotate(int[] nums, int k) {
    int n = nums.Length;
    k = k % n;
    if (k <= 0)
        return;

    int t = 0;
    for (int i = 0; i < k; i++) {
        t = nums[n - 1];
        for (int j = n - 1; j > 0; j--) {
            nums[j] = nums[j - 1];
        }
        nums[0] = t;
    }
}

优化方案2：三次反转法（最优原地解法，O(n)时间，O(1)空间） #

这是该题的经典最优解法，通过三次反转实现原地旋转，时间复杂度降至O(n)，空间复杂度为O(1)：

1. 反转整个数组
2. 反转前k个元素
3. 反转剩余的n-k个元素

对应的C#实现：

public void Rotate(int[] nums, int k) {
    int n = nums.Length;
    k = k % n;
    if (k == 0) return;

    // 反转整个数组
    Reverse(nums, 0, n - 1);
    // 反转前k个元素
    Reverse(nums, 0, k - 1);
    // 反转剩余元素
    Reverse(nums, k, n - 1);
}

private void Reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

优化方案3：额外数组法（O(n)时间，O(n)空间） #

如果允许使用额外空间，也可以直接通过数组拷贝实现，代码更直观：

public void Rotate(int[] nums, int k) {
    int n = nums.Length;
    k = k % n;
    if (k == 0) return;

    int[] temp = new int[n];
    // 拷贝后k个元素到新数组开头
    Array.Copy(nums, n - k, temp, 0, k);
    // 拷贝前n-k个元素到新数组后半部分
    Array.Copy(nums, 0, temp, k, n - k);
    // 拷贝回原数组
    Array.Copy(temp, nums, n);
}

内容的提问来源于stack exchange，提问作者Matteo