一个算法题,该如何处理

2012-02-25

一个算法题有两个数组，大小都为n，两个数组里有相同的元素，设计一个算法，找到两个数组中相同的元素。要求时

一个算法题
有两个数组，大小都为n，两个数组里有相同的元素，设计一个算法，找到两个数组中相同的元素。要求时间复杂度低。

最简单方法当然是将一个数组中的每个元素都与另外一个数组中的元素依次比较。但是最坏情况下的时间复杂度是n*n，效率太差。

我的解决方法：
用hashtable，设计一个hash函数，使得每个值的hash值不相同（要保证这个不知道会不会很难）。对每个值求hash值，如果有冲突，则是相同元素。时间复杂度为n

大家还有别的更好的设计不？欢迎大家回帖。分不够继续加。

[解决办法]
要求时间复杂度低就用哈希挺好的
[解决办法]
如果两个数组有序，可以向归并排序那样用两个指针从头部往后逐个比较。
无序的话，可以用stl的map，先把第一个数组的存进去，然后find第二个数组的每个元素，找到的话就是相同的数。这个不用考虑hash的冲突问题。
复杂度要低，还是用hash比较好，用sgi stl的hashmap也不错。
[解决办法]
用LCS可以不
[解决办法]
用hash不用保证每个hash值都相同吧，即使有hash冲突也行，例如用链地址法解决hash冲突
[解决办法]
用位图算法，之前那个数组进入位图，然后后面的判断是否位置为1，来确定是否会存在相同元素~~~~用空间换时间.
[解决办法]

C/C++ code

#include <string>#include <iostream>#include <set>using namespace std;int main(int argc, char* argv[]){    char* pStr1 = "1212324356dasdasdasdsad";    char* pStr2 = "asfcsdfsdaftrfejnmgfh3123123";    set<char> set_char1;    set<char> set_char2;    for(int i = 0;i < strlen(pStr1);i ++)        set_char1.insert(pStr1[i]);    for(i = 0;i < strlen(pStr2);i ++)    {        if(!set_char1.insert(pStr2[i]).second)            set_char2.insert((pStr2[i]));    }    for(set<char>::iterator it = set_char2.begin();it != set_char2.end();it ++)    {        cout << * it;    }    cout <<endl;    while(1);    return 0;}
[解决办法]
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
using namespace std;

int main(int argc, char* argv[]) {
   string str1("1212324356dasdasdasdsad");
   string str2("asfcsdfsdaftrfejnmgfh3123123");
   multiset<char> set1(str1.begin(), str1.end());
   multiset<char> set2(str2.begin(), str2.end());
   set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), ostream_iterator<char>(cout,""));
   return 0;
}

热点排行

软件架构设计

一个算法题,该如何处理