LeetCode: 189.旋转数组¶
1、题目描述¶
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: [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]
示例 2:
输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]
说明:
- 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的原地算法。
2、解题思路¶
2.1 缓冲数组法¶
设置一个与当前数组同样大小的数组,将原数组中的所有的元素使用取余,计算出位置,直接赋值
2.2 单步移动法¶
每一次右旋移动一次,根据需要移动的数量,多次移动
2.3 分组法¶
分组法较为巧妙
例如,1,2,3,4,5,6,7
我们想要右移3位,那么实际上可以如何实现呢?
我们将1,2,3,4只有移动到右面底部,然后将5,6,7平移到左面,就得到结果了
但是,如果想要不借助其他的空间移动,我们发现,直接取反就可以做到,不过1,2,3,4的位置是反着的,5,6,7的位置也是反着的
因此,根据移动的步数,进行分组,然后将组内部元素取反,再整体取反,就得到想要的结果了
void reverse(int *nums, int left, int right) { int length = right - left + 1; if (length <= 1) { return; } for (int i = 0; i < length / 2; i++) { nums[left + i] ^= nums[right - i]; nums[right - i] ^= nums[left + i]; nums[left + i] ^= nums[right - i]; } } void rotate(int *nums, int numsSize, int k) { int step = k % numsSize; if (step == 0) { return; } reverse(nums, 0, numsSize - step - 1); reverse(nums, numsSize - step, numsSize - 1); reverse(nums, 0, numsSize - 1); }