本文共 1364 字,大约阅读时间需要 4 分钟。
题目描述:
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例:
输入: [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]
❗解决思路❗:
? 1、刚开始,按照解释的步骤一步步走,基础例子能通过,但数组长度非常之大时,会超时。
class Solution {public: void rotate(vector & nums, int k) { for (int i = 0; i < k; ++i) { int temp = nums[nums.size()-1]; for (int j = nums.size() - 1; j > 0; --j) { nums[j] = nums[j-1]; } nums[0] = temp; } }};
? 2、这道题可以找一找规律,走 k 步的结果是什么呢?我们可以看到,走 k 步后,数组后 k 个数走到了数组的最前面,其余的数字依次后移。想一想,也就是说,数组的前 k 个数变成了数组的后 k 个数,且不考虑这 k 个数的顺序,我们怎么可以做到这一点呢?就是把数组整体翻转。 ( [1, 2, 3, 4, 5, 6, 7] → [7, 6, 5, 4, 3, 2, 1] )
经过上面的步骤后,我们发现,前 k 个数和后面 len-k 个数,其顺序完全颠倒,所以我们又可以将前 k 个数进行一次翻转,后 len-k 个数进行一次翻转。( [7, 6, 5, 4, 3, 2, 1] → [5, 6, 7, 1, 2, 3, 4] )
题目中已经说了 k 是非负数,所以我们不需要考虑这种情况了。但还有一点要注意,k 的大小和数组长度 len 的大小关系,所以在进行翻转之前,先要进行一步运算:k = k % nums.size()
class Solution {public: void rotate(vector & nums, int k) { //reverse(nums, 0, nums.size()-1); //reverse(nums, 0, k-1); //reverse(nums, k, nums.size()-1); // 防止 k > nums.size() k = k % nums.size(); reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin()+k, nums.end()); return; }};
转载地址:http://lstai.baihongyu.com/