一道笔试题讨论
题的大意是这样的：
有两等长数组A，B，所含元素相同，但顺序不同，只能取得A数组某值和B数组某值进行比较，比较结果为大于，小于，等于，但是不能取得同一数组A或者B中两个数进行比较，也不能取得某数组中的某个值，找到一个好的算法实现正确 匹配，（即A数组中某值与B中某值等值），分析算法时间复杂度，写出算法思路即可。
[解决办法]
#include <iostream>
using namespace std;
void matching(int a[],int b[],int k)
{
int i = 0;
while(i <= k)
{
int j = 0;
while(j <= k)
{
if(a[i] == b[j])
{
cout < < "( " < < i < < ", " < < j < < ") ";
break;
}
j++;
}
i++;
}
cout < < endl;
}
int main()
{
int a[10] = {1,2,3,4,5,6,7,8,9,10};
int b[10] = {10,6,4,5,1,8,7,9,3,2};
int k = sizeof(a)/sizeof(int);
matching(a,b,k);
return 0;
}
根据自己理解来写的 LZ看看是不是这个意思？
时间复杂度：o（n^2）
[解决办法]
1）在A数组中随机选取一个数，（根据题意，我们并不知道这个值的确定值是多少）比如说 A[i] ,然后和B 数组中进行比较，根据你的数据结构，将B数组每个数与A[i]进行比较，若比 A[i] 大的按照从后向前存储，比 A[i] 小的从前向后存储，要是等于A[i] ,就记录下来 这个值在B的位置 j,继续比较，直到B中数组全部比较完成，然后再把这个相等的b[j] 插入空余的那个中间位置上。
意思就是二分法
二分法解这个问题可以
[解决办法]
（注意，在这里，只更新相等的那个数值的 "标记 "， "某数在A中的位置 ",其它与A[k]不相同，或大，或小的情况下，不更新，即还保持A[i] 的比较结果，以利于继续比较）
========================
为什么不将B[j]后的值全更新呢？
以下为我的思路：
1。从A0出发。第一步同。（和B 数组中进行比较，根据你的数据结构，将B数组每个数与A[i]进行比较，若比 A[i] 大的按照从后向前存储，比 A[i] 小的从前向后存储，要是等于A[i] ,就记录下来 这个值在B的位置 j,继续比较，直到B中数组全部比较完成，然后再把这个相等的b[j] 插入空余的那个中间位置上。）
这里，j已经为一个定值。下面的m,p相同
2。考虑A1。与Bj比较。若A1大，则比较A1与Bj后的数。并更新C中Bj后的全部。计与A1相同的值为Bm。若A1小，同理。
3。考虑A2。先与Bj比较(假设上一步中A1比Bj大)：
3.1若A2大，则与Bm比较。
3.1.1若A2大，更新Bm后的全部。计与A2同者为Bp。
3.1.2若A2小，更新Bj~Bm中的全部。计与A2同者为Bp。
3.2若A2小。更新Bj前的全部。
4。考虑A3。同理。
－－－－－
在以后的步骤里，A中的数，如A[i]。与C中的数比较时，应该先与C最中间（若最中间数据尚未确定，则取最靠近）的数据比较。若A[i]属于C的后半部分，则再与后半部分的中间的数据相比。也就是尽量靠近使用二分法。
有什么不妥请指点。
