给你一个数组，将数组中的元素向右轮转 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 - 10 <= k <= 105
进阶：
- 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为
O(1) 的 原地 算法解决这个问题吗？
思路
问题的难度在于仅借助复杂度的空间，使得数组向前移动位。蛮力算法需要花费时间，我们考虑迭代版本。
假设从开始，每次移动位，那么移动的序列就是： 当然为了保证下标始终在之间，我们需要将下标对取模。我们关心的问题是，从出发点开始，移动到第几次时又回到了出发点？即对与一个整数，有 不难证明，为该线性同余方程的一个解。即 这就是说，序列 实际上被划分为了个同余类，也就是一次迭代过程中我们可以使得个元素归位。因为个元素模有个同余类，所以为使个元素全部归位，我们需要迭代次。
class Solution {
public void rotate(int[] nums, int k) {
int move = 0, s = 0, tmp = 0;
int len = nums.length;
k %= len;
while (move < len) {
tmp = nums[s];
int i = s, j = (i - k + len) % len;
while (j != s) {
nums[i] = nums[j];
i = j; j = (i - k + len) % len;
move++;
}
nums[i] = tmp;
s++; move++;
}
return;
}
}
|
时间复杂度仅为线性。
借助倒置算法的版本比较简单，参照PPT上的解释即可，这里不再赘述。
复杂度
