解题思路:
\qquad 首先要理解轮转的含义,轮转 = 将数组末尾元素移动至首位。轮转k
不为负数,那如果k
大于数组长度时会发生什么?定义n
为数组长度,当k == n
时,数组元素的顺序又恢复成初始状态,下一次轮转又与k = 1
结果相同。由此可知,有效的轮转数需要对数组长度取余,即k % n
。
\qquad 1)镜像轮转
\qquad 由于,末尾元素向前移动,会导致其他所有元素位置的改变,时间复杂度高;但如果换个角度,k次轮转,也可以看做n - k
个队首元素移动至队尾,这样一来,只需要将前n - k
个元素按顺序添加至数组中,操作后的数组取[n-k, n + n-k]
的片段输出即可。vector片段截取可以通过其成员函数assign()
完成。
void rotate(vector<int>& nums, int k) {int n = k % nums.size();int m = nums.size() - n;for(int i = 0; i < m; i++){nums.push_back(nums[i]);}nums.assign(nums.begin()+m, nums.end());}
\qquad 2)镜像翻转
\qquad 此外,轮转后的数组,后面的元素在前,前面的元素在后,将数组翻转过来是符合这个规律的。比如[1,2,3,4,5,6,7], k = 3
轮转后得到[5,6,7,1,2,3,4]
,观察翻转后的数组是[7,6,5,4,3,2,1]
,刚好数组的前半部分、和后半部分分别翻转就可以变成轮转后的结果,因此只需要进行三次翻转即可完成。翻转可以使用algorithm库自带的reverse()
实现。
void rotate(vector<int>& nums, int k) {reverse(nums.begin(), nums.end());k = k % nums.size();reverse(nums.begin(), nums.begin()+k);reverse(nums.begin()+k, nums.end());}