给定一个整形数组要求把其中的零元素移动到数组的末尾 非零元顺序保持不变
以下采用两种方法实现
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <windows.h> void PrintArr( int arr[], int iSize )
{
if( iSize < 0 )
return; int i = 0;
for( ; i < iSize; i++ )
{
if( !arr[i] )
printf( "%d ", arr[i] );
} puts( "" );
} void LocalMove( int arr[], int iSize )
{//本地移动 速度极慢 优点是消耗内存空间少
if( iSize <= 1 )
return; int i,j; int iZeroCount = 0;//零元总数 for( i = 0; i < iSize; i++ )
{
if( !arr[i] )
iZeroCount++;
} int iZeroCur = iZeroCount; for( i = 0; i < iSize && iZeroCur > 0; i++ )
{
if( !arr[i] )
{
for( j = i; j < iSize - ( iZeroCount - iZeroCur ); j++ )
{
arr[j] = arr[j+1];
} arr[j-1] = 0;
iZeroCur--;
i--;
}
} //PrintArr( arr, iSize );
} int* CreateIntArr( int iSize )
{//创建整形数组
puts( "CreateArr" ); int* pIntArr = (int*)malloc( sizeof( int ) * iSize ); if( !pIntArr )
return NULL; srand( iSize ); int i = 0;
for( ; i < iSize; i++ )
{
if( 0 == i % 2 )
*( pIntArr + i ) = rand();
else
*( pIntArr + i ) = 0;
} puts( "Finish create array!" ); return pIntArr;
} int* CopyArr( int* pArrInt, int iSize )
{//复制整形数组
if( !pArrInt || iSize <= 0 )
return NULL; int* pNewArr = (int*)malloc( sizeof( int ) * iSize ); if( !pNewArr )
return NULL; puts( "Starting copy array ..." );
int i = 0;
for( ; i < iSize; i++ )
{
*( pNewArr + i ) = *( pArrInt + i );
} puts( "Finish copy array..." ); return pNewArr;
}
void SaveMove( int arr[], int iSize )
{//空间换时间 这个算法的速度是上个算法速度的8万倍以上 这个专卖值得做
if( iSize <= 1 )
return; int i = 0;
int iNoneZero = 0; for( ; i < iSize; i++ )
{
if( arr[i] )
iNoneZero++;
} int* pIntArr = (int*)malloc( sizeof( int ) * iNoneZero );
int iCur = 0;
for( i = 0; i < iSize && iNoneZero > 0; i++ )
{
if( arr[i] )
{
*(pIntArr + iCur++) = arr[i];
iNoneZero--;
}
} memset( arr, 0, iSize );
for( i = 0; i < iCur; i++ )
{
arr[i] = *( pIntArr + i );
} //PrintArr( arr, iSize );
} int main( int argc, char* argv[] )
{
if( argc < 2 )
{
puts( "Usage: MoveZero.exe number" );
return -1;
} int iNum = atoi( argv[1] ); if( iNum <= 0 )
{
puts( "Error argument!" );
} int* pIntArrOne = CreateIntArr( iNum );
int* pIntArrTwo = CopyArr( pIntArrOne, iNum ); long lStart; lStart = GetTickCount();
puts( "LocalMove" );
LocalMove( pIntArrOne, iNum );
printf( "LocalMove Cost Time: %ld\n", GetTickCount() - lStart ); lStart = GetTickCount();
puts( "SaveMove" );
SaveMove( pIntArrTwo, iNum );
printf( "SaveMove Cost Time: %ld\n", GetTickCount() - lStart ); return 0;
}
测试结果如下:
C:\Users\fzql>"F:\MyDocument\Visual Studio 2008\Projects\VCInterview\VCInterview
\Debug\VCInterview.exe" 102400
CreateArr
Finish create array!
Starting copy array ...
Finish copy array...
LocalMove
LocalMove Cost Time: 16208
SaveMove
SaveMove Cost Time: 0
C:\Users\fzql>"F:\MyDocument\Visual Studio 2008\Projects\VCInterview\VCInterview
\Debug\VCInterview.exe" 1024000
CreateArr
Finish create array!
Starting copy array ...
Finish copy array...
LocalMove
LocalMove Cost Time: 1377832
SaveMove
SaveMove Cost Time: 16