/************************************************************************
      长度确定的数组大小为m＋n（m、n各自大小不确定），
    编写程序将前m个元素与后n个元素交换，要求空间复杂度
 降到最小，时间复杂度尽量最小。
************************************************************************/
#include
#include

template
void Swap2(T &x, T &y)
{
 T  temp;

 temp = x;
 x    = y;
 y    = temp;
}

// 把values数组的前nCount个元素与从nPos位置开始的nCount个元素交换位置
template
void SwapN(T values[], int nPos, int nCount)
{
 int  i;

 for(i=0; i {
  Swap2(values[i], values[nPos+i]);
 }
}

// 交换数组values的前m个元素和后n个元素的位置
// 借鉴辗转相除法的思想进行辗转移动
template
void SwapMN(T values[], int m, int n)
{
 int  nCurPos = 0;
 int  nMin;

 nMin = m assert(nMin >= 0);

 while(nMin > 0)
 {
  SwapN(values+nCurPos, m, nMin);
  nCurPos += nMin;
  if(m >= n)
  {
   m -= n;
  }
  else
  {
   n -= m;
  }
  nMin = m }
}

void Output(int values[], int n)
{
 int  i;

 printf("\nResult is: \n");
 for(i=0; i {
  printf("%d  ", values[i]);
 }
 printf("\n");
}
 
int main()
{
 int  test[20] = {1,2,3,4,5,6,7,8, 9, 10, 11, 12,13,14,15,16,17,18,19};
 int  m = 13, n = 6;

 SwapMN(test, m, n);
 Output(test, m+n);

 return 0;
}

评论