给定一个整形数组要求把其中的零元素移动到数组的末尾 非零元顺序保持不变
以下采用两种方法实现
#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 ", GetTickCount() - lStart ); lStart = GetTickCount(); puts( "SaveMove" ); SaveMove( pIntArrTwo, iNum ); printf( "SaveMove Cost Time: %ld ", GetTickCount() - lStart ); return 0; }
测试结果如下:
C:Usersfzql>"F:MyDocumentVisual Studio 2008ProjectsVCInterviewVCInterview
DebugVCInterview.exe" 102400
CreateArr
Finish create array!
Starting copy array ...
Finish copy array...
LocalMove
LocalMove Cost Time: 16208
SaveMove
SaveMove Cost Time: 0
C:Usersfzql>"F:MyDocumentVisual Studio 2008ProjectsVCInterviewVCInterview
DebugVCInterview.exe" 1024000
CreateArr
Finish create array!
Starting copy array ...
Finish copy array...
LocalMove
LocalMove Cost Time: 1377832
SaveMove
SaveMove Cost Time: 16