给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: [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]
要求使用空间复杂度为 O(1) 的 原地 算法。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rotate-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k = k%nums.size();
if(k == 0)
return;
int i, j, j0, count = 0, prev, next = nums[0];
for(i = 0; count < nums.size(); ++i)
{
j0 = i;
prev = nums[j0];
while(i != j)
{
j = (j0+k)%nums.size();
next = nums[j];
nums[j] = prev;
j0 = j;
prev = next;
++count;
}
}
}
};
n=7, k=3
原数组 : 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 --> 结果
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k = k%nums.size();
if(k == 0)
return;
reverse(nums.begin(), nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k, nums.end());
}
};