189.轮转数组

LeetCode LeetCode 热题100 数组双指针数学

发布时间 : 2000-01-10 01:08

字数:1.9k 阅读 :

评论:

189.轮转数组

189.轮转数组

189.1 题目

给定一个整数数组 nums，将数组中的元素向右轮转 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 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

189.2 题解

方法一：使用额外数组

思路

最直观的方法：创建一个新数组，把每个元素放到它轮转后的位置。

关键公式：元素 i 轮转 k 步后的新位置是 (i + k) % n。

注意：k 可能大于数组长度，所以要先取模 k = k % n。

举个例子：nums = [1,2,3,4,5,6,7], k = 3

位置0的1 → 新位置(0+3)%7=3
位置1的2 → 新位置(1+3)%7=4
位置2的3 → 新位置(2+3)%7=5
位置3的4 → 新位置(3+3)%7=6
位置4的5 → 新位置(4+3)%7=0
位置5的6 → 新位置(5+3)%7=1
位置6的7 → 新位置(6+3)%7=2
结果：[5,6,7,1,2,3,4]

复杂度分析

时间复杂度：O(n)，遍历两次数组
空间复杂度：O(n)，额外数组

代码

// 方法一：使用额外数组
static void Rotate1(int[] nums, int k)
{
    int n = nums.Length; // 获取数组长度
    k = k % n; // 处理 k 大于数组长度的情况，取模运算保证 k 在合理范围内
    int[] rotated = new int[n]; // 创建一个与 nums 长度相同的额外数组

    for (int i = 0; i < n; i++) // 遍历原数组
    {
        rotated[(i + k) % n] = nums[i]; // 将元素放置到新位置
    }

    for (int i = 0; i < n; i++) // 将新数组的值复制回原数组
    {
        nums[i] = rotated[i]; // 复制每个元素
    }
}

方法二：三次反转法

思路

一个巧妙的原地算法：通过三次反转实现轮转。

原理：把数组分成两部分 [A | B]，轮转后变成 [B | A]。

先反转整个数组：[A | B] → [B' | A']
再反转前 k 个：[B' | A'] → [B | A']
最后反转剩余部分：[B | A'] → [B | A]

举个例子：nums = [1,2,3,4,5,6,7], k = 3

原数组：[1,2,3,4,5,6,7]，分成 [1,2,3,4] 和 [5,6,7]
反转全部：[7,6,5,4,3,2,1]
反转前3个：[5,6,7,4,3,2,1]
反转后4个：[5,6,7,1,2,3,4] ✓

复杂度分析

时间复杂度：O(n)，每个元素被访问两次
空间复杂度：O(1)，原地修改

代码

// 方法二：三次反转法
static void Rotate2(int[] nums, int k)
{
    int numsLength = nums.Length; // 获取数组长度
    k = k % numsLength; // 处理 k 大于数组长度的情况，取模运算保证 k 在合理范围内

    Reverse(nums, 0, numsLength - 1); // 第一次反转，反转整个数组
    Reverse(nums, 0, k - 1); // 第二次反转，反转前 k 个元素
    Reverse(nums, k, numsLength - 1); // 第三次反转，反转剩余的元素
}

// 反转数组的辅助函数
static void Reverse(int[] nums, int start, int end)
{
    while (start < end) // 只要起始索引小于结束索引就进行反转
    {
        // 交换 nums[start] 和 nums[end]
        (nums[start], nums[end]) = (nums[end], nums[start]); // 使用元组解构进行交换
        start++; // 增加起始索引
        end--; // 减少结束索引
    }
}

189.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个整数数组 nums，将数组中的元素向右轮转 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 <= nums.length <= 105
        // -231 <= nums[i] <= 231 - 1
        // 0 <= k <= 105
        //
        // 进阶：
        // 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
        // 你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 1, 2, 3, 4, 5, 6, 7 }; // 初始化示例1的数组
        int k1 = 3; // 初始化示例1的 k 值
        Rotate1(nums1, k1); // 调用方法1进行轮转
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(",", nums1)}]"); // 打印方法1的输出
        nums1 = new int[] { 1, 2, 3, 4, 5, 6, 7 }; // 重新初始化数组以便使用方法2
        Rotate2(nums1, k1); // 调用方法2进行轮转
        Console.WriteLine($"示例1 方法2 输出：[{string.Join(",", nums1)}]"); // 打印方法2的输出

        // 示例 2
        int[] nums2 = { -1, -100, 3, 99 }; // 初始化示例2的数组
        int k2 = 2; // 初始化示例2的 k 值
        Rotate1(nums2, k2); // 调用方法1进行轮转
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(",", nums2)}]"); // 打印方法1的输出
        nums2 = new int[] { -1, -100, 3, 99 }; // 重新初始化数组以便使用方法2
        Rotate2(nums2, k2); // 调用方法2进行轮转
        Console.WriteLine($"示例2 方法2 输出：[{string.Join(",", nums2)}]"); // 打印方法2的输出

        #endregion
    }

    #region 答案

    // 方法一：使用额外数组
    static void Rotate1(int[] nums, int k)
    {
        int n = nums.Length; // 获取数组长度
        k = k % n; // 处理 k 大于数组长度的情况，取模运算保证 k 在合理范围内
        int[] rotated = new int[n]; // 创建一个与 nums 长度相同的额外数组

        for (int i = 0; i < n; i++) // 遍历原数组
        {
            rotated[(i + k) % n] = nums[i]; // 将元素放置到新位置
        }

        for (int i = 0; i < n; i++) // 将新数组的值复制回原数组
        {
            nums[i] = rotated[i]; // 复制每个元素
        }
    }

    // 方法二：三次反转法
    static void Rotate2(int[] nums, int k)
    {
        int numsLength = nums.Length; // 获取数组长度
        k = k % numsLength; // 处理 k 大于数组长度的情况，取模运算保证 k 在合理范围内

        Reverse(nums, 0, numsLength - 1); // 第一次反转，反转整个数组
        Reverse(nums, 0, k - 1); // 第二次反转，反转前 k 个元素
        Reverse(nums, k, numsLength - 1); // 第三次反转，反转剩余的元素
    }

    // 反转数组的辅助函数
    static void Reverse(int[] nums, int start, int end)
    {
        while (start < end) // 只要起始索引小于结束索引就进行反转
        {
            // 交换 nums[start] 和 nums[end]
            (nums[start], nums[end]) = (nums[end], nums[start]); // 使用元组解构进行交换
            start++; // 增加起始索引
            end--; // 减少结束索引
        }
    }

    #endregion
}

189.4 运行结果

示例1 方法1 输出：[5,6,7,1,2,3,4]
示例1 方法2 输出：[5,6,7,1,2,3,4]
示例2 方法1 输出：[3,99,-1,-100]
示例2 方法2 输出：[3,99,-1,-100]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com