急，跪求，日本公司面试试题 C++ vector 算法
去日本公司面试试题如下整数の配列去日本公司面试试题A、vectorBは任意の整数が格納されています。それぞれの配列の中で、整数はユニークであるとします。この両方の配列に格納されている同じ整数を抜き出し、新しい配列vectorCを作成してください。
※与えられた配列のサイズが大きい場合のことを考え、パフォーマンスが良くなるようにしてください。
中文
在整数型数列vectorA和vectorB中，记录着任意的整数数据。在每个整数型数列中，其所记述的整数数值都是独一不重复的。编写一个程序，把两个数列中都含有的相同的整数抽出，做成一个新的数列vectorC。
※设想数列的行数很大，即数据非常多的情况下，怎样既能实现题目的要求，又能达到性能良好。
哪位大侠，能给出具体算法么？？？
#include "stdafx.h"
#include <vector>
void Test1_1( const vector <int>& vectorA, const vector <int>& vectorB, vector <int>& vectorC )
{
}
请各位C＋＋牛人，帮我解决，谢谢了。 --------------------编程问答-------------------- 不知道性能好不好。。。。
就当抛砖引玉了。
做的不好，楼主别嫌弃……嘿嘿嘿嘿。。。。
厚着脸皮贴代码了：
--------------------编程问答-------------------- 代码测试过了。。。。vat，vbt各6000数据，倒是能立即出结果，不用等待。耗时没有测试过。。。。
vector<int> getSameVectors(vector<int> vat,vector<int> vbt)
{
vector<int> vct;
int idx;
int i,j;
idx=0;
sort(vat.begin(), vat.end());
sort(vbt.begin(), vbt.end());
for(i=0; i < vbt.size();i++)
{
for(j=idx;j < vat.size();j++)
{
if(vbt[i] < vat[j])
{
idx=j;
break;
}
else if(vbt[i]==vat[j])
{
vct.push_back (vbt[i]);
idx=j;
break;
}
}
if(vbt[i]>vat[vat.size()-1])
{
break;
}
}
return vct;
}
纯C++的代码不会测耗时。。。。
希望高手指正，自学C++中，望得到指引。 --------------------编程问答-------------------- VA19万条记录
VB都是21万条
取出VC是3万++条
耗时20毫秒左右。 --------------------编程问答-------------------- 如果不是有序的，就只能遍历了 --------------------编程问答-------------------- 1）先排序
2）然后用两个指针（迭代器）分别指向两个数列A,B的头部
3）比较大小，小的则指针向后移，有相等的存入C。
4）重复4直至比较完。
时间复杂度O(nlogn) --------------------编程问答-------------------- 2008下是11--14秒不等，上面的20毫秒是因为排序不耗时（vectoraA与vectorB内的数据本身有序）。
打乱顺序之后的耗时11-14秒。。。。这还是大片有序，整体无序的情况。。。
但是如果不排序的话，耗时更多。。。。
void Test1_1( const vector <int>& vectorA, const vector <int>& vectorB, vector <int>& vectorC )
{
}
这个函数内的vectorA和vectorB另两个vector<int> VA和VB来取代操作（const不许排序）
空间的损耗，总是好过时间损耗
VA和VB赋值成vectorA和vectorB，基本不耗时。
--------------------编程问答-------------------- stl本身就是很的树结构，内部优化很好。时间一般是花在自已写的代码上了 --------------------编程问答-------------------- 在C++ PRIMER中有专门讲这个泛型算法的，有一个专有函数就是从两个容器中选择出相同的数据，我一下想不起来了，书不在身边，查到了再给你留言
建议你学习一下C++ PRIMER --------------------编程问答-------------------- 没有楼上各位达人所讲的那么复杂，那个泛型算法自己可以将两个容器中的相同数据取出，并保存在另一个新的同类容器中，效率没的说，是自带的泛型算法 --------------------编程问答-------------------- 用动态规划吧，相当于求两个字符串的公共部分 --------------------编程问答-------------------- 学习中 慢慢体会中 --------------------编程问答-------------------- 先sort,然后二分查找,给分,这二个函数 stl 自带,效率没的说 --------------------编程问答--------------------
#include <iostream>
#include <vector>
#include <algorithm>
int main(int argc, char **pArgv)
{
int arrayA[] = {0, 3, 4, 5, 20, 2, 39, 90, 78};
int arrayB[] = {1, 3, 44, 5, 244, 2, 39, 490, 400};
std::vector<int> veA(arrayA, arrayA + 9);
std::vector<int> veB(arrayB, arrayB + 9);
std::vector<int> veC;
std::sort(veA.begin(), veA.end());
std::sort(veB.begin(), veB.end());
for (size_t i = 0; i < veA.size(); i++)
{
if (std::binary_search(veB.begin(), veB.end(), veA[i]))
veC.push_back(veA[i]);
}
std::copy(veC.begin(), veC.end(), std::ostream_iterator<int>(std::cout, ","));
std::cout << std::endl;
} --------------------编程问答-------------------- 顶一下~！
补充：.NET技术 , VC.NET
