盒子
盒子
文章目录
  1. Nim编程早茶
    1. 借助辅助数组
    2. 原地算法

Nim语言如何循环旋转数组

Nim编程早茶

Nim 编程实现循环移动(rotate)数组,提供两种方法。一种 O(n) 的原地算法,一种借助辅助数组的算法,都十分简洁。

借助辅助数组

时间复杂度 O(n)。

shift 表示移动的方向及元素个数。正数表示循环左移,负数表示循环右移。所以当 shift 为负数的时候,我们需要加上周期(数组的长度) 。当 shift 超过数组长度,我们通过取模操作,得到固定区间的移动数值。

我们找到分界点,将分界点后面的 shift 个元素搬移到 0 ~ divPoint 的位置上。其他元素则搬移到分界点之后的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
proc roll*[T](input: seq[T], shift: int = 1): seq[T] =
if shift == 0:
return input
let size = input.len
var s: int = shift
while s < 0:
s += size
s = s mod size
result = newSeq[T](size)
let divPoint = size - s
for j in 0 ..< divPoint:
result[j] = input[j+s]
for j in divPoint ..< size:
result[j] = input[j+s-size]

原地算法

shift 参数的处理,同前面相同。

我们只需 reverse(0, shift - 1), reverse(shift, n-1), reverse(0, n-1) ,即可完成循环移动的操作。reverse 表示反转操作,01234 -> 43210

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import algorithm


proc roll*[T](input: var seq[T], shift: int = 1) =
if shift == 0:
return
let size = input.len
var s: int = shift
while s < 0:
s += size
s = s mod size
reverse(input, 0, s - 1)
reverse(input, s, input.high)
reverse(input)

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
when isMainModule:
block:
# 循环左移
assert roll(@[1, 3, 4, 5], 2) == @[4, 5, 1, 3]
# 循环右移
assert roll(@[1, 3, 4, 5], -1) == @[5, 1, 3, 4]
block:
var a = @[1, 3, 4, 5]
# 循环左移
roll(a, 2)
assert a == @[4, 5, 1, 3]
# 循环右移
roll(a, -3)
assert a == @[5, 1, 3, 4]