旋转数组的k位置性能c#

Question

我在LeetCode上解决问题，并参考这个问题:189。旋转数组

给定一个数组，将该数组向右旋转k步，其中k是非负的。

示例1:

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

我给出了我的解决方案:

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;
}
}

我的问题不是关于解决方案，而是关于它的性能。

我可以改进的解决方案，使更快吗?还是我的方法不对?

因为它通过了所有的测试用例，但是它失败了最后一个原因是一个大数组，里面有大的数字，它在足够快时失败了，它给了我

<时间限制>

Answer 1

您可以在单个while循环中运行它。我没有leetcode，所以我不能测试，我只能在本地运行如果你运行这个，你会得到什么?此外，它不做原地移动，所以如果有内存测试，它可能会失败。

public static int[] Rotate(int[] nums, int k) {
if (k <= 0) return nums;
var n = new int[nums.Length];
var stopAt = nums.Length - k;
while(stopAt < 0) {
stopAt = nums.Length - Math.Abs(stopAt);
}
var i = stopAt;
var y = 0;
while (true) {
n[y] = nums[i];
y++;
i++;
if (i >= nums.Length) {
i = 0;
}
if (i == stopAt) break;
}
return n;
}

Answer 2

执行此操作有一个技巧，它涉及两个步骤的转换。O(n)时间，O(1)空间。

示例，k = 3:

1234567

首先将n-k所描绘的两个部分中的每一部分反向放置:

4321 765

现在反转整个数组:

5671234

为读者提供了一个练习。

Answer 3

如果您正在寻找性能，您可以摆脱嵌套循环以获得O(n)时间复杂度与O(n * n):

1. 计算result数组的每一项应该是什么
2. 复制result数组到初始数组
代码:

public void Rotate(int[] nums, int k) {
int[] result = new int[nums.Length];

for (int i = 0; i < nums.Length; ++i) {
int index = (i + k % nums.Length + nums.Length) % nums.Length;

result[index] = nums[i];
}

Array.Copy(result, nums, nums.Length);
}

注意，一般情况下我们有一个相当复杂的index公式:

int index = (i + k % nums.Length + nums.Length) % nums.Length;

我们应该准备好负k(而index不能为负)和巨大的k(可能的整数溢出)。如果k >= 0和k <= 1e5如Leet Code所述，我们可以将index简化为

int index = (i + k) % nums.Length;

并有紧解

public void Rotate(int[] nums, int k) {
int[] result = new int[nums.Length];

for (int i = 0; i < nums.Length; ++i) 
result[(i + k) % nums.Length] = nums[i];

Array.Copy(result, nums, nums.Length);
}

编辑:为什么index公式中出现%(余数)?

让我们看看发生了什么。当i + k小于nums.Length时，只在i + k索引处写值。当i + k == nums.Length我们应该写在index == 0，当i + k == nums.Length + 1我们应该写在index == 1，…，当i + k == nums.Length + r时，我们应该写在index == r，注意r == (i + k) % nums.Length == (nums.Length + r) % nums.Length == 0 + r == r