一道面试题:
provider a method and test it:
input: int [], like 1,2,3,3,3,3,3,3,3,4,3,3,2,4,4
function: provider a method move mumber is adjacent and duplicated with the prior one, result like 1,2,3,4,3,2,4 ( only remove the number marked red : 1,2,3,3,3,3,3,3,3,4,3,3,2,4,4)
output:the int array moved number is adjacent and duplicated with the prior one: like 1,2,3,4,3,2,4
此题贴出来有一段时间了,现更新一下:
我一位同事给出的结果(下面在notepad中写的,没有编译过),空间和时间复杂度都为(n),当然还有其他的一些算法解决,但都没有达到空间和时间复杂度都为(1*n).
如果有更好或其他的方法,请留言.谢谢!
//return value is the new size of the array after removing the duplicate
int RemoveDuplicate(int *a,int size){
int newArrayPointer=0;
for(int i=1;i<size;i++)
{
if(a[i]!=a[newArrayPointer])
{
a[++newArrayPointer]=a[i];
}
}
return newArrayPointer+1;
}