189.轮转数组

LeetCode LeetCode 数组双指针数学

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

字数:1.5k 阅读 :

评论:

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 题解

使用额外数组

// 方法一：使用额外数组
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--; // 减少结束索引
    }
}

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