All About Programming: 算法题28 配对比较---有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量一样，把配对的石头和木头找出来 - 在水一方 - 博客频道

解题思路：此题就是需找两个可比较数列的问题。如果直接比较的话，那就是O(n^2)的复杂度。

设a[1...n]，b[1...n]为两个序列。那么可以新建这样的两个实数数列

c[1...n], cn = bn - a1

d[1...n], dn = an - b1+c1 = an-a1.

由题意知，cn中没有重复的值，dn中也没有重复的值。

因此问题转化为求两个实数数列cn和dn中的值相等的数对。

可采用并查集的思路来解决这个问题：时间复杂度O(n),空间复杂度O(n)

算法：

1）建立一个hashmap表--nodemap，如STL中的map，C#中的Dictionary，key为ci，value为计算ci时bi在b中的索引或计算的di在a中的索引。

2) for i = 1 to n 计算ci = bi-a1，如果ci在nodemap中，这数对(a[nodemap[ci]], b[i])，配对成功，否则nodemap中插入节点(ci, i)

计算di = (ai-b1)+(b1-a1)，如果di在nodemap中，则数对(a[i], b[nodemap[di]])匹配成功，否则插入节点(di, i).

Labels