//问题: //给你一个数组，a[]={1,1,1,1,1,2,2,2,2,3,3,3,4,5,6} //要输出的结果是1,2,3,4,5,6.(去除重复的数字,要求时间空间的考虑).#include <iostream>using namespace std;template<int _N>class Bitset{public:Bitset(){_Tidy();//调用_Tidy()函数会初始化所有位为0.}void Show()//显示01位.{for(int _I=0;_I<_N;_I++){cout<<(test(_I)?'1':'0');}}bool test(int _P)//测试该位置是否为真(1).{int _I = _P/32;return (A[_I]>>(_P%32))&0x1;}void _Tidy(){for(int _I=0;_I<_W;_I++){A[_I] = 0;}}void set(int _P)//将_p下标设置为1.{int _I = _P/32;A[_I] |= (0x1<<(_P%32));}void printf(){for(int _I=0;_I<_N;_I++){test(_I) && (cout<<_I<<" ");}}//打印排列结果.private:typedef long LONG;//以long的4个字节为一个单位数组.enum{_Nw=(_N-1)/(sizeof(LONG)*8),_W=_Nw+1};int A[_W];};int main(){Bitset<600> a;int b[]={1,1,1,1,2,2,3,3,34,2,423,42,34,23,1,1,3,213,123,21,3,3,4,32,543,5,46,3,45,35,23,42,3};for(int i=0;i<33;i++){a.set(b[i]);}a.printf();}
下面有两种粗暴的方法。
#include <iostream> using namespace std;struct Node {int data;Node *next;Node():data(-1),next(NULL){} }; //时间复杂度大幅度减少，但是增加了一定的空间复杂度。 class Hash {public:Hash(int a[],int n){NodeTable = new Node[7];for(int i=0;i<n;i++){int index = HashIndex(a[i]);//寻找a[i]的下标，并且在hash表查找该值是否存在，不存在我们则以链表形式插入。NodeTable[index].data=1;//初始化为-1，表示在该下标下面没有数值，如果出现index等于该下标则将该下标标记为1，表示有东西存着呢！Node* p = NodeTable[index].next;while(p!=NULL && p->data!=a[i]){p=p->next;}if(p==NULL){Node *s = new Node();s->data = a[i];NodeTable[index].next=s;}}}void Show(){for(int i=0;i<7;i++){if(NodeTable[i].data!=-1){Node *p = NodeTable[i].next;while(p!=NULL){cout<<" "<<p->data<<" ";p = p->next;}}}cout<<endl;}int HashIndex(int x){return x%7;}private:Node *NodeTable; }; int main() {int a[]={1,2,2,1,1,1,3,4,5};Hash sh(a,9);sh.Show();return 0; }————————————————————– #include <iostream> #include <stdlib.h> using namespace std; //粗暴的删减法，时间复杂度稍微高了一些，空间复杂度比较低。 void Grial(int a[],int& n)//这里的n用引用传入，因为数组大小会在我删减重复数值时动态改变,引用传入，我就不需要记录n的实际值了。 {int i=0;int j;int k;for(;i<n;){for(j=i+1;j<=n;j++){if(a[i]==a[j]){for(k=j;k<n;k++){a[k]=a[k+1];//删除与a[i]重复的值，并且将n减1；}n–;}if(j>=n){i++;}}if(a[i]==a[i+1]){for(k=i;k<n;k++){a[k]=a[k+1];}n–;}}} int main() {int a[100];for(int i=0;i<100;i++){a[i]=rand()%100;}int b=99;Grial(a,b);for(int i=0;i<b;i++){cout<<a[i]<<endl;}return 0; }
，为你的快乐而快乐的是朋友，为你的难过而难过的才是你的知己。
