题目描述
给定一个整数数组 nums,将数组中的元素向右轮转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]
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
算法1
字符串翻转
时间复杂度
两轮翻转都是遍历O(n),因此时间复杂度为O(n)
C++ 代码
class Solution {
public:
/*
联想到字符串翻转:
hello world 变成 world hello
1、先进行整个翻转:dlrow olleh
2、再进行逐个翻转:world hello
轮转k个位置后的结果就是上述字符串翻转后的结果,但此处我们不需要将数字变为字符串,直接分为两部分处理就可
把多个数字分为两个"字符串",左边部分 :位于k个元素之前的其他元素,右边部分:末尾k个元素
1 2 3 4 5 6 7 k=3 -> 5 6 7 1 2 3 4
_______ _____ _____ _______
类似于 "1234 567" -> "567 1234"
因此翻转流程相同,只是处理的数据类型不同
翻转流程如下:
1 2 3 4 5 6 7 k=3 -> 5 6 7 1 2 3 4
整个翻转 : 7 6 5 4 3 2 1
前k个(即 7 6 5)和后面再次分开翻转 : 5 6 7 1 2 3 4
注意:该题的k有可能是0,也有可能是nums.size()的倍数,这两种情况都可以不翻转,因此进行特判处理
*/
void rotate(vector<int>& nums, int k) {
int nSize=nums.size();
k%=nSize; // 0与任何数取余都是0,因此可以和k为nums.size()的情况放在一起
if(!k) return; // k为0 或 k为nums.size()的倍数 则直接返回
// 整个翻转
reverse(nums.begin(),nums.end());
// 左右两部分分别进行翻转,翻转技巧(两个指针两边走,互相交换)
int i=0,j=k-1;
while(i<=j)
{
swap(nums[i],nums[j]);
++i,--j;
}
i=k,j=nSize-1;
while(i<=j)
{
swap(nums[i],nums[j]);
++i,--j;
}
}
};