By Leo_璇哥

更新日期:

文章目录

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

思路：一次遍历数组找出绝对值最大的数，以便确定哈希表的大小。

第二次遍历数组，当遇到第一次出现的数，则放入应该放的位置（仍在原数组中），如果重复则不放入。

VS2010中测试正确代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<span style="font-size:14px;">#include<iostream>  
using namespace std;  
  
typedef struct Info  
{  
    Info():isPos(0),isNeg(0){}  
    bool isPos;  
    bool isNeg;  
}HashTable;  
  
int main()  
{  
    int a[] = {1,2,0,2,-1,999,3,999,88,-1,2,2,2,-1,4,4,44,444,44,444,4444};  
    int max = INT_MIN;//#define INT_MIN     (-2147483647 - 1) /* minimum (signed) int value */  
  
    for(int i=0;i<sizeof(a)/sizeof(a[0]);++i)  
    {  
        cout<<a[i]<<" ";  
    }  
    cout<<endl;  
  
    for(int i=0;i<sizeof(a)/sizeof(a[0]);++i)  
    {  
        if(abs(a[i])>max)  
            max = abs(a[i]);  
    }  
  
    HashTable* hash = new HashTable[max+1];  
      
    int toReplace=0;  
     for(int current=0;current<sizeof(a)/sizeof(int);++current)  
     {  
         if(hash[abs(a[current])].isPos==0 && hash[abs(a[current])].isNeg==0)  
         {  
             if(a[current]>0 || a[current] == 0)  
                 hash[abs(a[current])].isPos=1;  
             if(a[current]<0)  
                 hash[abs(a[current])].isNeg=1;  
  
             a[toReplace] = a[current];  
             toReplace++;  
         }  
         else  
         {  
             //确定重复  
             if(hash[abs(a[current])].isPos==1 && (a[current]>0 || a[current]==0))  
                continue ;  
              if(hash[abs(a[current])].isNeg==1 && a[current]<0)  
                continue ;  
              else  
              {//不重复  
                   if(a[current]>0 || a[current] == 0)  
                        hash[abs(a[current])].isPos=1;  
                     if(a[current]<0)  
                         hash[abs(a[current])].isNeg=1;  
                     
                     a[toReplace] = a[current];  
                    toReplace++;  
              }  
         }  
     }  
  
     for(int i=0;i<toReplace;++i)  
    {  
        cout<<a[i]<<" ";  
    }  
    cout<<endl;  
  
    system("pause");  
    return 0;  
}</span>
文章目录