const int SIZE = 100; int a[SIZE], n;它记录着一个长度为 n 的序列 a
[1], a[2], …, a[n]。
现在需要一个函数,以整数 p (1 ≤ p ≤ n)为参数,实现如下功能:将序列 a 的前 p 个数与后 n – p 个数对调,且不改变这 p 个数(或 n – p 个数)之间的相对位置。例如, 长度为 5 的序列 1, 2, 3, 4, 5,当 p = 2 时重排结果为 3, 4, 5, 1, 2。
有一种朴素的算法可以实现这一需求,其时间复杂度为 O(n)、空间复杂度为 O(n):
procedure swap1(p : longint);
var
i, j : longint;
b : array[1..SIZE] of longint;
begin
for i := 1 to p do
b[1] := a[i]; //(2 分)
for i := p + 1 to n do b[i - p] := a[i];
for i := 1 to n do
a[i] := b[i];
end;
我们也可以用时间换空间,使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法:
procedure swap2(p : longint); var i, j, temp : longint; begin for i := p + 1 to n do begin temp := a[i]; for j := i downto 2 do //(2 分) a[j] := a[j - 1]; 3 := temp; //(2 分) end; end;
事实上,还有一种更好的算法,时间复杂度为 O(n)、空间复杂度为 O(1):
procedure swap3(p : longint); var start1, end1, start2, end2, i, j, temp : longint; begin start1 := 1; end1 := p; start2 := p + 1; end2 := n; while true do begin i := start1; j := start2; while (i <= end1) and (j <= end2) do begin temp := a[i]; a[i] := a[j]; a[j] := temp; inc(i); inc(j); end; if i <= end1 then start1 := i else if 4 then //(3 分) begin start1 := 5; //(3 分) end1 := 6 ; //(3 分) start2 := j; end else break; end; end;