一、题目
给定一个整数数组 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. 搞清楚题目给的数组变化逻辑——轮换k个位置其实就是把[l-k,l-1]的这几个元素放到[0,k-1]的位置上去；
2. 明显可以看到如果是线性表，在轮换过程中会引起很多移动，时间复杂度高，在这里选择哪种方式来优化会引出多种解法——
① 解法一思路：
题目提到原地修改的要求，想到双指针，又想到双指针的核心思想——两头开工。在这个问题中我们就可以分成要往前挪的一头和往后挪的一头，这种情况下怎么样才能减少移动？
我们可以使用两个指针，一个指针从数组的开头开始，另一个指针从数组的末尾开始。通过交换这两个指针指向的元素，可以在不需要额外空间的情况下完成轮换。具体步骤如下：
- 首先，将数组分成两部分：前
l-k个元素和后k个元素。 - 使用两个指针，一个指向前
l-k个元素的末尾，另一个指向后k个元素的开头。 - 交换这两个指针指向的元素，直到两个指针相遇。
- 最后，将前
l-k个元素和后k个元素分别进行反转，即可得到轮换后的数组。
这种方式是原地修改，很符合题目要求。
② 解法二思路：
移动的规律使得数组移动前后对应位置的元素也有规律，为了避免在原数组上进行复杂的移动操作，可以创建一个新的数组 news 来存储轮转后的结果。新数组的长度与原数组相同，即 l。
- 对于原数组中的每个元素
nums[i]，其在新数组中的位置可以通过(i + k) % l计算得出。 - 这个公式的意义是：将原数组的索引
i向右移动k个位置，如果超出数组长度，则通过取模运算% l回到数组的开头。 - 例如，对于
nums[0]，其新位置是(0 + k) % l，对于nums[1]，其新位置是(1 + k) % l，依此类推。
但是这种方式并非原地修改，而是定义新数组来处理。
③ 解法三思路：
几乎每种语言都有自带的切片和拼接函数，这个问题显然也可以用到。方法也很直接，把要挪到后面的l-k个元素和要挪到前面的k个元素都切下来换个顺序拼一起即可。
需要注意的是切片拼接后也是返回一个新数组而不是原地修改nums。
补充一点不同语言中切片和拼接函数的用法：
| 切片函数 | 拼接函数 | |
| JavaScript |
|
|
|
|
|
|
|
|
| C++ | 使用 vector--sliced |
vector--insert string--append或者+ |
|
|
|
| Python
|
比如：
|
比如：
参数：需要拼接的两个或多个序列。 |
|
|
三、代码
解法一（原地修改+反转）
① JS：
function ChangeOver(nums, k) {
let l = nums.length;
k = k % l;
// 使用反转的方法进行原地修改
reverse(nums, 0, l - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, l - 1);
}
function reverse(nums, start, end) {
while (start < end) {
let temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}② Python：
def change_over(nums, k):
l = len(nums)
k = k % l
reverse(nums, 0, l - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, l - 1)
def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1③ C++：
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start++;
end--;
}
}
void ChangeOver(vector<int>& nums, int k) {
int l = nums.size();
k = k % l;
reverse(nums, 0, l - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, l - 1);
}
解法二（找规律+新数组）
① JS：
function changeOver(nums,k){
let l = nums.length;
let news = new Array(l);
k = k % l; // 处理 k 大于数组长度的情况
for(let i = 0; i < l; i++) {
news[(i + k) % l] = nums[i];
}
return news;
}
// let nums1 = [1, 2, 3, 4, 5, 6, 7];
// let k1 = 3;
// console.log(changeOver(nums1, k1));
// 上述部分用于测试输出② Python：
def change_over(nums, k):
l = len(nums)
k = k % l
news = [0] * l # 创建一个长度为 l 的新数组
for i in range(l):
news[(i + k) % l] = nums[i]
return news③ C++：
vector<int> changeOver(vector<int>& nums, int k) {
int l = nums.size();
k = k % l;
vector<int> news(l);
for (int i = 0; i < l; i++) {
news[(i + k) % l] = nums[i];
}
return news;
}解法三（切片+拼接）：
① JS：
function changeOver(nums,k){
let l = nums.length;
k = k % l; // 处理 k 大于数组长度的情况
return nums.slice(-k).concat(nums.slice(0, -k));
}② Python：
def change_over(nums, k):
l = len(nums)
k = k % l
return nums[-k:] + nums[:-k]③ C++：
vector<int> changeOver(vector<int>& nums, int k) {
int l = nums.size();
k = k % l; // 处理 k 大于数组长度的情况
vector<int> result;
// 将后 k 个元素添加到结果中
for (int i = l - k; i < l; i++) {
result.push_back(nums[i]);
}
// 将前 l-k 个元素添加到结果中
for (int i = 0; i < l - k; i++) {
result.push_back(nums[i]);
}
return result;
}四、总结
1. 处理k<l的这个约束条件时，用k=k%l代替while(k<l)来简化代码。取模运算是一个常数时间操作，能够直接计算出 k 在数组长度范围内的等效值，非常适合处理轮转次数大于数组长度的情况。
2. 原地修改这一要求使得解法二、三无法通过力扣题解，解法一之外还有哪些更优的解法尚需进一步思考和尝试。