C言語ゼロシフト操作
3427 ワード
整形配列を指定するには、ゼロ要素を配列の末尾に移動する非ゼロ要素順序を一定に保つ必要があります.
以下に2つの方法で実現する
テスト結果は次のとおりです.
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
以下に2つの方法で実現する
#include
#include
#include
#include
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:\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