以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  求助：数组元素交换的问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=38713)

--  作者：gina81827yanke
--  发布时间：10/10/2006 2:25:00 PM

--  求助：数组元素交换的问题
给定数组a[0:n-1]以及一个正整数k（0<=k<=n-1），设计一个算法，将子数组a[0:k]和
a[k+1:n-1]交换位置，要求算法在最坏的情况下耗时O(n)，且用到的辅助空间为O(1)。
--  作者：Logician
--  发布时间：10/11/2006 5:31:00 PM

--  
template <class T>
void Exchange(T A[], int k, int n)
{
    int i, length1=k+1, length2=n-k-1;
    for(i=0;i<n;i++)
        swap(A[i],A[n-i-1]);
    for(i=0;i<length2;i++)
        swap(A[i],A[length2-i-1]);
    for(i=0;i<length1;i++)
        swap(A[i+length2],A[n-i-1]);
}


[此贴子已经被作者于2006-10-12 1:07:09编辑过]
--  作者：vingo555
--  发布时间：10/12/2006 10:50:00 AM

--  
以下是引用Logician在2006-10-11 17:31:00的发言：
template <class T>
void Exchange(T A[], int k, int n)
{
     int i, length1=k+1, length2=n-k-1;
     for(i=0;i<n;i++)
         swap(A[i],A[n-i-1]);
     for(i=0;i<length2;i++)
         swap(A[i],A[length2-i-1]);
     for(i=0;i<length1;i++)
         swap(A[i+length2],A[n-i-1]);
}


思想正确，实现的却有个小小的bug


[此贴子已经被作者于2006-10-12 1:07:09编辑过]


--  作者：Logician
--  发布时间：10/13/2006 11:04:00 AM

--  
哦？请指教。：）

PS：我没调试的。：）

--  作者：DavidPotter
--  发布时间：10/17/2006 9:47:00 AM

--  
for(i=0;i<n;i++)
        swap(A[i],A[n-i-1]);
这句没有作用。
走一半就好了。。。
后面的也一样。

--  作者：Logician
--  发布时间：10/17/2006 11:01:00 AM

--  
哦。对。否则又换回去了……
：）
--  作者：gina81827yanke
--  发布时间：10/18/2006 9:36:00 AM

--  
呵呵，了解，基本思想就是做三个逆序
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 78.125ms