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