经典的面试算法问题--去除数组中重复数据--O(n)？

Question

有一个整型数组，用O(n)的算法来去掉里面重复的项目。有人知道吗？ 我知道用hashtable或者位运算应该可以，但是不知道位运算代码怎么写下面是我写的用hashtable结果String数组的方案，整型一样的，不知道是否可以改进         public String[] compact(String input[]){

String output[] = new String[input.length];
int m = 0;
Hashtable hash = new Hashtable();

for (int i=0; i<output.length; i++){
if (!hash.containsKey(input[i])){
hash.put(input[i], i);
output[m]=input[i];
m++;
}
}
return output;
}

Answer 1

这是C++里头的,你改成JAVA即可
template<class   T>   
  void   UniqueArray(T   *array,int   &len){   
  int   i,j,k;   
  for(i=0;i<len;i++)   
  for(j=i+1;j<len;j++)   
  if(array[i]==array[j])   
  {   
  for(k=j;k<len;k++)   
  array[k]=array[k+1];   
  len--;   
  j--;   
  }   
  }另一种是:#include  <stdio.h > 
#include  <stdlib.h > int main(int argc, char *argv[]) 
{ 
  int   array[]   =   {1,   2,   0,   2,   -1,   999, -1,  3,   999,   88};  
  int len = sizeof(array)/sizeof(array[0]); 
  int i,j; 
   
  for (i=0; i <len; i++) 
  { 
    for (j=i+1; j <len; j++) 
    { 
       if (array==array[j]) 
       { 
           len--; 
           array[j] = array[len]; 
            
           
       } 
     } 
  } 
  for (i=0; i <len; i++) 
  { 
    printf ("%d ",array); 
  } 
  system("PAUSE"); 
  return 0; 
}

Answer 2

发现自己SB了。
不需要这个判断的
if (!hash.containsKey(input[i])){ 
改成 if (hash.get(input[i])==null){ 简单多了！！

Answer 3

我是要O(n)的方案。。你给我的是O(n*n+n)的。。应该是用位运算的。

Answer 4

java的
public static String removeRepeat(String str){
String temp = "";

for(int i = 0 ; i<str.length(); i++){
char tempChar = str.charAt(i);
if(temp.indexOf(tempChar)==-1){
temp = temp+tempChar;
}

}
return temp;
}

Answer 5

如果要线性的话，那么可以采用空间换时间的做法：
#define INVALID 999999

Answer 6

如果要线性的话，那么可以采用空间换时间的做法：
#include <memery.h> 
#define INVALID 999999
int src[100];int unique(int n, int* src, int* ans)
{
    int i,j;
    int* tmp;
    tmp = (int*)malloc(n*sizeof(int*));
    memset(tmp,INVALID,n*sizeof(int));
    for(i = 0; i < n; i++)
    {
        if(*(tmp+*(src+i)) == INVALID)
            *(tmp+*(src+i) = *(src+i);
    }
    j = 0;
    for(i = 0; i < n; i++)
    {
        if(*(tmp + i) != INVALID)
            *(ans+j++) = *(tmp + i);
    }
    return j;
}