解决的问题很简单: 就是若干个数，判断各不相同！
代码写的很烂,我只是验证一下.
速度还可以,几十万个数也就是一眨眼的工夫
因为用树的收敛速度很快, 当然这只是针对随机数列,对于不重复随机数列的复杂度平均为O(n*log2(n)) 空间占用小于4n
最坏的情况下的复杂度就比较糟糕了,可以设想一下一个单调递增或递减的数列,其复杂度达到O(n^2),空间占用4n
想验证的而内存少的同志请把MAXNUM改小点,没准会出错(偶没检查分配内存的返回值)
想打印出结果来的请用重定向到一个文件比如 ./tree 2>lj.txt
只想看看速度的./tree就可以了
代码如果简单的扩展一下还可以用来统计数字重复出现的次数,效率也是跟上面一样的
#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAXNUM 500000typedef struct tree { int a; struct tree *r; struct tree *l;};void detree(struct tree *node){ if( node==NULL) return; detree(node->r); detree(node->l); free(node);}int main(int argc,char *argv[]){ int i; bool flag = true; int zhengshu[MAXNUM]; struct tree *root; struct tree *temp; struct tree *rt; struct tree *lt; srand(time(NULL)); for (i = 0; i < MAXNUM; i++) { zhengshu[i] = rand(); } if(argc==2) { int ktemp=rand()%MAXNUM; int itemp=rand()%MAXNUM; zhengshu[ktemp]=zhengshu[itemp]; printf("[%d]=[%d]=%d\n",ktemp,itemp,zhengshu[itemp]); for (i = 0; i < MAXNUM; i++) { printf("[%d]=%d\n", i,zhengshu[i]); } } root=(tree *)malloc(sizeof(tree)); root->a = zhengshu[0]; root->r = NULL; root->l = NULL; for (i = 1; i < MAXNUM; i++) { temp = root; do { if ((zhengshu[i] != temp->a)) { if (zhengshu[i] > temp->a) { if (NULL != temp->r) { temp = temp->r; if (zhengshu[i] == temp->a) { flag = false; printf("\t[%d]=%d have a same one\n",i,zhengshu[i]); break; } } else { rt = (tree *) malloc(sizeof(tree)); temp->r = rt; rt->a = zhengshu[i]; rt->r = NULL; rt->l = NULL; break; } } else { if (NULL != temp->l) { temp = temp->l; if (zhengshu[i] == temp->a) { flag = false; printf("\t[%d]=%d have a same one\n",i,zhengshu[i]); break; } } else { lt = (tree *) malloc(sizeof(tree)); temp->l = lt; lt->a = zhengshu[i]; lt->r = NULL; lt->l = NULL; break; } } } 上一页 下一页
