设计一个算法,将含有 n 个整数元素的数组 a[0..n-1]循环右移 m 位。要求算法的空间复杂度为 O(1)。
时间: 2024-10-28 20:07:54 浏览: 38
数据结构(JAVA) 将含有n个整数元素的数组a0..n-1循环右移m位,要求算法的空间复杂度为O(1)
这个问题可以使用“原地”(In-place)旋转数组的技巧来解决,空间复杂度为O(1),即只需要常量级别的额外空间。以下是算法步骤:
1. **验证输入合法性**:首先检查 `m` 是否在合法范围内,即 `0 <= m < n`。
2. **计算实际旋转次数**:由于数组是循环的,所以当 `m >= n` 时,实际上只旋转了 `m % n` 次。
3. **使用临时变量交换**:
- 初始化两个指针,一个指向起始位置 `i = 0`,另一个指向 `m % n` 之后的位置 `j = (n + m - 1) % n`。
- 使用临时变量 `temp` 存储当前值 `a[i]`。
- 循环 `k` 从 `i+1` 到 `j`(包括边界),每次循环都将 `a[k]` 的值赋给 `temp`,然后将 `temp` 赋给 `a[k-1]`,直到 `i` 和 `j` 相遇。
- 当 `i == j` 时停止循环,此时 `a[i]` 已经放到了原数组的末尾,完成了右移。
以下是伪代码描述:
```python
function rotateArray(a[], n, m):
if m < 0 or m >= n:
return
m = m % n
for i from 0 to m-1:
temp = a[i]
j = (i+m) % n
while j != i:
a[j] = a[j+1]
j = (j+1) % n
a[j] = temp
```
阅读全文