j*****h
发帖数: 62 | 1 可以定义f(a,b) = a<<32 +b
这样对，任何一个node，都能得到唯一的f(a,b)。
扫描一便该list，对每个点一个（假设为{a,b}），计算 f(a,b)，并将其插入
一个hash表。然后计算f(b,a)，到hash表里面去找,找到了就是该node的对偶点.
复杂性O(n) | t*******l
发帖数: 3662 | 2 to fix your solution:
for each pair {a,b},
create a string "b_a", check if it is in the hashtable, if yes,
a 对偶 node is found.
otherwise, create a string "a_b" and insert into hashtable.
then continue. | s*i
发帖数: 5025 | 3 1. Make two groups
Group A, i<=j
Group B, i>j
linear time
2. Make a hashtable for group A, use i as key and j as value
(At the same time, do some mark work on identical nodes. i==j cases should
be finally calculated)
linear
3. for each in group B, use n as key to retrieve value in the table
and compare the value to m.
linear |
|
