出个题，求每个pair的hamming distance - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

出个题，求每个pair的hamming distance

出个题，求每个pair的hamming distance# JobHunting - 待字闺中

s*r2013-05-14 07:05

1 楼

If I refuse to send you to the airport in one morning and ask you to find
another friend to do it for you for no apprant reason--that is a cardinal
sin because it has undermined the basic foundation of a couple. On the other
hand, if I refuse to drive you to the airport, but asked you to hire a
shuttle to do the job, that maybe unsatisfactory, but nothing from sinful.

x*w2013-05-14 07:05

2 楼

给一个数组，求每个pair的hamming distance之和，要优于n^2

c*p2013-05-14 07:05

3 楼

目测要用分治？

d*n2013-05-14 07:05

4 楼

suppose the array is int array
int HammingDistance(int A[], int N)
{
int hammingDist = 0;
for(int i = 0; i < 32; ++i)
{
int Ones = 0;
for (int j = 0 ; j < N; ++j)
Ones += (A[j] >> i) & 1;
hammingDist += Ones * (N - Ones);
}
return hammingDist;
}
Is this correct?

【在 x*********w 的大作中提到】

: 给一个数组，求每个pair的hamming distance之和，要优于n^2

x*w2013-05-14 07:05

5 楼

没仔细看，
大概是O(N), 按bit求得解法是正解

【在 d****n 的大作中提到】

: suppose the array is int array
: int HammingDistance(int A[], int N)
: {
: int hammingDist = 0;
: for(int i = 0; i < 32; ++i)
: {
: int Ones = 0;
: for (int j = 0 ; j < N; ++j)
: Ones += (A[j] >> i) & 1;
: hammingDist += Ones * (N - Ones);

s*r2013-05-14 07:05

6 楼

每个pair的hamming distance？
没看懂。。。