给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: 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]
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
自己写的代码
public class Solution
{
public void Rotate(int[] nums, int k)
{
int frequency = k;
if (k > nums.Length)
{
frequency = k % nums.Length;
}
while (frequency > 0)
{
int temp = nums[nums.Length - 1];
for (int i = nums.Length - 1 - 1; i >= 0; i--)
{
nums[i + 1] = nums[i];
}
nums[0] = temp;
frequency--;
}
//foreach (var item in nums)
//{
// Console.WriteLine(item);
//}
}
}
时间复杂度过高
官方题解为
解法一
思路和算法
最直观的做法是创建一个新数组，存储原数组旋转后的元素，然后将新数组中的元素复制回原数组。
假设原数组 nums 的长度是 n，则创建长度相等的新数组 newNums 存储旋转后的元素。根据旋转规则，对于 0≤i<n，有 newNums[(i+k)modn]=nums[i]。
填入新数组 newNums 的元素之后，将新数组 newNums 的元素复制回原数组 nums 即可。
public class Solution {
public void Rotate(int[] nums, int k) {
int length = nums.Length;
int[] newNums = new int[length];
for (int i = 0; i < length; i++) {
newNums[(i + k) % length] = nums[i];
}
for (int i = 0; i < length; i++) {
nums[i] = newNums[i];
}
}
}
