快速查找的有关问题

快速查找的问题
]需要实现的功能：几十万大小的数组，实现数组间的找重。比如有
type data1[n], data2[n],data3[n]......;
data1,data2,data3...之间一一对应，n大小为几十万，怎么快速实现data1找重，然后按data1类型分类。
之前用的vector<type>存放，用find函数查找，但是发现速度太慢。还有什么好的方法吗？请各位大神指点。。。快速查找的有关问题

------解决方案--------------------
换一种思路，将data[n]
变成N[data]。这样data就是下标，有多少个数就是N，查找就变成直接访问下标的事了。
------解决方案--------------------

引用:

]需要实现的功能：几十万大小的数组，实现数组间的找重。比如有
type data1[n], data2[n],data3[n]......;
data1,data2,data3...之间一一对应，n大小为几十万，怎么快速实现data1找重，然后按data1类型分类。
之前用的vector<type>存放，用find函数查找，但是发现速度太慢。还有什么好的方法吗？请各位大神指点。。。

没看懂题目。。。
但是看明白了，用vector，肯定是线性时间复杂度O（n）的，对于几十万来说，效率当然低了。使用数组下标，仍然是O（n），vector就是一个高级的动态数组，没多大区别。

使用散列表是可行的。
这个问题要达到高效率，至少要使用一个复杂度在O（logn）的查找算法。典型的二分法、树形结构存储，二叉树，堆。
------解决方案--------------------
仅供参考

//文件1中的内容排序并去重,结果保存到文件2中

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAXCHARS 128      //能处理的最大行宽,包括行尾的\n和字符串尾的\0

int MAXLINES=10000,MAXLINES2;

char *buf,*buf2;

int c,n,hh,i,L;

FILE *f;

char ln[MAXCHARS];

int ignore_case=0;

int icompare(const void *arg1,const void *arg2) {

   return stricmp((char *)arg1,(char *)arg2);

}

int compare(const void *arg1,const void *arg2) {

   return strcmp((char *)arg1,(char *)arg2);

}

int main(int argc,char **argv) {

    if (argc<3) {

        printf("Unique line. Designed by zhao4zhong1@163.com. 2012-08-20\n");

        printf("Usage: %s src.txt uniqued.txt [-i]\n",argv[0]);

        return 1;

    }

    if (argc>3) ignore_case=1;//若存在命令行参数3，忽略大小写

    f=fopen(argv[1],"r");

    if (NULL==f) {

        printf("Can not find file %s!\n",argv[1]);

        return 1;

    }

    buf=(char *)malloc(MAXLINES*MAXCHARS);

    if (NULL==buf) {

        fclose(f);

        printf("Can not malloc(%d LINES*%d CHARS)!\n",MAXLINES,MAXCHARS);

        return 2;

    }

    n=0;

    hh=0;

    i=0;

    while (1) {

        if (NULL==fgets(ln,MAXCHARS,f)) break;//

        hh++;

        L=strlen(ln)-1;

        if ('\n'!=ln[L]) {//超长行忽略后面内容

            printf("%s Line %d too long(>%d),spilth ignored.\n",argv[1],hh,MAXCHARS);

            while (1) {

                c=fgetc(f);

                if ('\n'==c 
------解决方案--------------------
 EOF==c) break;//

            }

        }

        while (1) {//去掉行尾的'\n'和空格

            if ('\n'==ln[L] 
------解决方案--------------------
 ' '==ln[L]) {

                ln[L]=0;

                L--;

                if (L<0) break;//

            } else break;//

        }

        if (L>=0) {

            strcpy(buf+i,ln);i+=MAXCHARS;

            n++;

            if (n>=MAXLINES) {

                MAXLINES2=MAXLINES*2;

                if (MAXLINES2==1280000) MAXLINES2=2500000;

                buf2=(char *)realloc(buf,MAXLINES2*MAXCHARS);

快速查找的有关问题

相关推荐