求一简单算法，从少量数据中找出不同,该怎么处理

求一简单算法，从少量数据中找出不同
本帖最后由 ITDeng 于 2012-07-25 21:12:41 编辑 小弟不太懂算法，请各位指教
例：
数据A：123，456，789，101，112
数据B：789，101，653，222，112
需要找出653，222
大家帮忙想个算法，谢谢了，尽量效率高的
[解决办法]
分两步完成：
1.对A,B两组数据排序，得到
  数据A'：101，112,123，456，789
  数据B'：101，112,222，653，789
  此步骤的效率可以达到O(n*logn).
2.在数据B'中找出没有在A'中出现的数据
  可以很快找到：222,653
  此步骤的效率是线性的，即：O(n).

故总的效率是O(n*logn).
[解决办法]
数据很少直接2重循环就完了，数据稍大的话如一楼排序，再大的话可以用hash
[解决办法]
字符串的话，先把A串每个加一个不会有的字符合并成一个串（比如@;等）形成123@456@789@101@112@
然后在这个字符串里面分别查找789@，101@，653@，222@，112@，找不到的就是你想要的
[解决办法]
排好一组，另外一组每个元素二分查找。字符的话也可以二分，就是判断字典顺序了。另外一种方法，两组合并成一组，排序，然后遍历，看那个元素不是两个。
[解决办法]
数学中差集的概念（在第二个集合但是不在第一个集合中的数据）
熟悉STL的话，可以直接用STL 算法库中提供的差集运算，这里给出用STL算法实现的代码，供参考(Good Luck)：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
/*
// input 2 group data by hand 

vector<string> strVec1;// store the first group data 
vector<string> strVec2;// store the second group data

string strTmp;

cout << "Please enter the 1st data(spit with space/enter, end with ctr+z):" << endl;

while(cin >> strTmp)
{
strVec1.push_back(strTmp);
}

cout << "Please enter the 2nd data(spit with space/enter, end with ctr+z):" << endl;

cin.clear();
while(cin >> strTmp)
{
strVec2.push_back(strTmp);
}
*/

// for demonstration

string str1[] = {"123","456","789","101","112"};
string str2[] = {"123","456","222","653","789"};

vector<string> strVec1(str1,str1+5);// store the first group data 
vector<string> strVec2(str2,str2+5);// store the second group data


vector<string> strVec3;// store the result (the difference set of 1st and 2nd group data)

sort(strVec1.begin(),strVec1.end());
sort(strVec2.begin(),strVec2.end());

set_difference(strVec2.begin(), strVec2.end(), strVec1.begin(), strVec1.end(), back_inserter(strVec3));

copy(strVec3.begin(),strVec3.end(),ostream_iterator<string>(cout,"  "));

cout << endl;
getchar();

return 0;
}