题目:你一个数组,将数组中的元素向右轮转 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]
要点:一般来说我是直接对于数组复制与另一个数组然后for循环替换位置,但这样做有些麻烦而且会很容易发生错误,然后还有另一个方法,就是我们可以使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度,我们遍历原数组,将原数组下标为 ii 的元素放至新数组下标为 (i+k)\bmod n(i+k)modn 的位置,最后将新数组拷贝至原数组即可。用取模的方式来计算是哪个位置。其中还有的问题就是,是去一个新值进行循环替代,还是找一个新数组进行复制以防移动的数覆盖原先的数,当然新数组肯定是方便一些。
结果:(暴力)class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> newArr(n);
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
nums.assign(newArr.begin(), newArr.end());
}
};
有一种更巧妙的的是反转:将所有元素反转。然后反转前 k 个元素,再反转后面 n-kn−k 个元素,就能得到想要的结果。
原始数组 : 1 2 3 4 5 6 7
反转所有数字后 : 7 6 5 4 3 2 1
反转前 k 个数字后 : 5 6 7 4 3 2 1
反转后 n-k 个数字后 : 5 6 7 1 2 3 4 --> 结果
代码:var rotate = function(nums, k) {
k=k%nums.length;
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
};
function reverse(arr,start,end){
while(start<end){
var temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}