原文转载自http://blog.csdn.net/breeze1998/article/details/5525284#comments
int A[nSize],其中隐藏着若干0,其余非0整数,写一个函数int Func(int* A, int nSize),使A把0移至后面,非0整数移至
数组前面并保持有序,返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题,注释规范且给出设计思路)
程序如下:不使用辅助空间
int Func(int* A, int nSize)
{
if(A == NULL)
{
return -1;
}
if(nSize < 1)
{
return 0;
}
int count = 0;
//计算所有为0的元素个数
for(int k = 0; k < nSize; k++)
{
if(A[k] != 0)
{
count++;
}
}
if(count == 0)
{
return count;
}
int i = 0;
int num = nSize;
while(i < num)
{
if(A[i] == 0)
{
// 其后所有元素前移
for(int j = i; j < nSize - 1; j++)
{
A[j] = A[j+1];
}
A[--num] = 0;
continue;
}
i++;
}
return count;
}
最好情况:该数组中没有为0元素,时间复杂度为O(n);
最坏情况:该数组中全部为0元素,时间复杂度为O(n/2*n/2);
自己的解法
int Func(int* A, int nSize)
{
int iReadPos = 0;
int iScanPos = 0;
if( NULL == A )
{
return (-1);
}
if( 1 > nSize )
{
return (0);
}
int i = 0;
while(iReadPos < nSize)
{
if( 0 == A[iReadPos] )
{
// 从上一次不为0的后一数据开始扫描
for(int iIndex = (iScanPos + 1); iIndex < nSize; iIndex++,iScanPos++)
{
if ( 0 != A[iIndex] )
{
A[iReadPos] = A[iReadPos] ^ A[iIndex];
A[iIndex] = A[iReadPos] ^ A[iIndex];
A[iReadPos] = A[iReadPos] ^ A[iIndex];
break;
}
}
}
if ( nSize == (iScanPos + 1) )
{
break;
}
iReadPos++;
}
return (iReadPos);
}
这个最大查找次数为n