学步园

66、微软面试题
请把一个整形数组中重复的数字去掉。例如： 
1,    2,    0,    2,    -1,    999,    3,    999,    88 
答案应该是：

1,    2，   0，  -1，  999，   3，  88 

/*
66、微软面试题
yaoha2003
请把一个整形数组中重复的数字去掉。例如： 
1,    2,    0,    2,    -1,    999,    3,    999,    88 
答案应该是：
1,    2，   0，  -1，  999，   3，  88 

为了节省时间，用hash表存储标记，但是不知道其大小，
所以先遍历一遍，绝对值最大的数，确定大小；
然后，有正负情况，用结构体表示 ，正数，负数的存在情况 
第二次遍历数组，已出现过步放入数组，用一个指针从头开始标记。 
*/
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
struct hashTable{
	int pos,neg;
	hashTable()
	{
		pos=0;
		neg=0;
	}
}; 
int main() 
{ 
	int a[] = {1,2,0,2,-1,999,3,999,88,1,2,2,2,-1,4,4,55,444,55,444,4444}; 
	int len,i,max,t,k;
	
	//输出原数组 
	len=sizeof(a)/sizeof(int);
	for(i=0;i<len;i++)
		printf("%d ",a[i]);
	printf("\n");
	
	//第一遍遍历 确定hash大小 
	max=-1;
	for(i=0;i<len;i++)
	{
		t=abs(a[i]);
		if(t>max)
			max=t;
	}
	hashTable *hash=new hashTable[max+1];
	
	k=0;//更新后的数组指针 
	for(i=0;i<len;i++)
	{
		if(a[i]>=0&&hash[a[i]].pos==1||a[i]<0&&hash[-a[i]].neg==1)//出现过 
			continue;
		if(a[i]>=0)//标记存在 
			hash[a[i]].pos=1;
		else
			hash[-a[i]].neg=1;
		a[k++]=a[i]; 
	}
	
	for(i=0;i<k;i++)//输出原数组 
		printf("%d ",a[i]);
	printf("\n");
	
	return 0; 
}