《编程珠玑》第三章
问题一：请将一个具有n个元素的一维向量x向左旋转i个位置。
例如，假设n=8，i=3，那么向量abcdefgh旋转之后得到向量defghabc。
简单编码，使用一个具有n个元素的中间向量，分n步即可完成功能。
你可以仅用几十字节的微小内存，花费与n成比例的时间来旋转向量么？
方案一：实现一个函数，用来将向量向左旋转1个位置。循环调用此函数i次即可。
本方案节省空间（只需要一个元素的额外存储），但是浪费了时间（需要做很多次中间操作的搬迁）。
1 int MAIN(vector x, int i, int n)
2 {
3 for (int ei = 0; ei < i; ei ++)
4 x = leftshift1(x, n);
5
6 return OK;
7 }
8
9 vector leftshift1 (vector & x, int n)
10 {
11 element first = x[0];
12
13 for (int ei = 0; ei < n; ei ++)
14 x[ei] = x[ei+1];
15
16 x[n - 1] = first;
17
18 return x;
19 }
方案二：将前i个元素复制到额外存储中，将后n-i个元素前移i个元素，再把额外存储中的数据拷贝到向量的最后i个空间里。
本方案使用了i个元素的额外存储，过于浪费空间。
1 int MAIN (vector x, int i, int n)
2 {
3 vector y = /*build vector with n elements*/
4
5 //copy i elements from top x to y
6 memcpy(y, x, i * sizeof(x[0]));
7
8 //copy n-i elements from end x to y
9 memmove(x, x + i, (n - i) * sizeof(x[0]));
10
11 //copy i elements from y to end x
12 memcpy(x + (n - i), y, i * sizeof(x[0]));
13
14 return OK;
15 }
方案三：设前i个元素为a，后n-i个元素为b。则向量x可以表示为 ab，转换后的向量可以表示为 ba。
而只需要将a和b分别转置得到 a'b'，再对整个向量进行转置，就可以得到最终的向量 ba。
本方案代码简洁清晰，只是计算量增加了一倍（多做了一次位移）。
1 int MAIN (vector x, int i, int n)
2 {
3 x = reserveVector(x, 0, i-1);
4 x = reserveVector(x, i, n-1);
5 x = reserveVector(x, 0, n-1);
6
7 return OK;
8 }
9
10 vector reserveVector(vector & x, int startPos, int endPos)
11 {
12 int s = startPos;
13 int e = endPos;
14
15 while(s < e)
16 {
17 swap(x[s], x[e]);
18 s ++;
19 e --;
20 }
21
22 return x;
23 }
24
25 int swap (element & s, element & e)
26 {
27 element t = s;
28 s = e;
29 e = t;
30 return OK;
31 }
方案四：直接计算各个元素的最终位置。
对于前i个元素，假设初始位置为t(0<=t<i)，则最终位置应该是 (n - i + t)
对于后 n-i 个元素，假设初始位置为t(i<=t<n)，则最终位置相当于前移了i，应该是 (t - i)
本方案的代码并没有前述方案的简洁，但是计算量最少，并且没有冗余的搬移。
1 int MAIN (vector x, int i, int n)
2 {
3 int s = 0;
4 int c = 0;
5 element f;
6
7 s = 0;
8 f = x[s];
9
10 while (c < n)
11 {
12 //get final position of current element s
13 int e = GetFinalPosition(s, i, n);
14
15 //store original value in current position to tmp value
16 element t = x[e];
17
18 //fill current element s into final position
19 x[e] = f;
20
21 //increase count
22 c ++;
23
24 //prepare for next
25 s = e;
26
27 //store original value from tmp value
28 f = t;
29 }
30
31 return OK;
32 }
33
34 int GetFinalPosition(int t, int i, int n)
35 {
36 if (t < i)
37 return (n - i) + t;
38
39 if ((t >= i) && (t < n))
40 return (t - i);
41
42 return t;
43 }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。