现在的位置: 首页 > 综合 > 正文

华为的一道面试题的解答(自己的另解)

2018年07月06日 ⁄ 综合 ⁄ 共 1072字 ⁄ 字号 评论关闭

原文转载自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

 

抱歉!评论已关闭.