leetcode 189轮转数组
class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); vectorintres(n,0); for(int i0;in;i){ res[(ik)%n] nums[i]; } nums res; } };这段代码的核心思路是先把每个元素放到旋转后的新位置再把结果赋值回原数组。例如原数组nums {1,2,3,4,5,6,7}; k 3;数组长度n 7;创建一个临时数组vectorint res(n, 0);然后遍历原数组把原来下标为i的元素放到(i k) % n这个新位置中。例如nums[0] 1原下标是0右移 3 位后(0 3) % 7 3所以res[3] 1;再比如nums[5] 6新下标(5 3) % 7 1所以res[1] 6;这里% n的作用就是超过数组末尾后重新绕回数组开头。全部移动完成后res {5,6,7,1,2,3,4};最后nums res;把旋转后的结果整体赋值回nums。因为nums是引用参数vectorint nums所以原数组也会真正被修改。可以直接记成一句话原位置i的元素右移k位后的新位置是(ik)%n全部放进res后再执行nums res。题解2翻转数组class Solution { public: void reverse(vectorint nums, int start, int end) { while (start end) { swap(nums[start], nums[end]); start 1; end - 1; } } void rotate(vectorint nums, int k) { k % nums.size(); reverse(nums, 0, nums.size() - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.size() - 1); } };nums -------; k 3 result -------; reverse ------- we can get ------- reverse -- we can get ------- reverse ----- we can get ------- this visualization help me figure it out :)
