小公司网站维护济南网络推广公司

题目链接：

189.轮转数组

题目描述：

解题思路：

要想实现数组元素向右轮转k个位置，可是将数组三次反转来实现

以 nums = [1,2,3,4,5,6,7], k = 3 为例，最终要得到[5,6,7,1,2,3,4]:

• 第一次反转：将整个数组反转得到 [7,6,5,4,3,2,1]
• 第二次反转：将前k个元素进行反转得到[5,6,7,4,3,2,1]
• 第三次反转：将最后n-k个元素进行反转得到[5,6,7,1,2,3,4]，n为数组nums长度

复杂度分析：

• 时间复杂度O(N)
• 空间复杂度O(1)

代码实现：

class Solution {
public:void reverse(vector<int>& nums, int start, int stop){int p1 = start;int p2 = stop;int temp;while(p2>p1){temp = nums[p1];nums[p1] = nums[p2];nums[p2] = temp;p1++;p2--;}}void rotate(vector<int>& nums, int k) {int n = nums.size();reverse(nums, 0, n-1);reverse(nums, 0, k%n-1);reverse(nums, k%n, n-1);}
};