g*****u
发帖数: 298 | 1 Each user ranks N songs in order of preference. Given a preference list,
find the user with the closest preferences. Measure "closest" according to
the number of inversions. Devise an N log N algorithm for the problem. | d**a
发帖数: 84 | 2 S1=n1,n2,...,nk
S2=m1,m2,...,mk
step1
先把s2转换成s1的下标，这个如果用hash可以theta(N)
然后就是一个标准问题，算inversion number
step2
divide and conquer, like merge sort,
在merge过程中同时算inversion
这个方法的问题是step1有点不是很爽，期待更好的方法
【在 g*****u 的大作中提到】
: Each user ranks N songs in order of preference. Given a preference list,
: find the user with the closest preferences. Measure "closest" according to
: the number of inversions. Devise an N log N algorithm for the problem.
|
|
