g********o
发帖数: 132 | 1 假设有300个二进制数 （每个二进制数都是30位）
1001001011111011110
1010101110111111001
1010111101110101110
1011111000000010101
..
..
..
..
1001001011111011110
1010101110111111001
1010111101110101110
1011111000000010101
所以就是，300行，30列
位置：每个二进制数（即每一行）最左边的一位为第1位，最右边的一位就是第30位。
现在需要输出：所有符合要求的两个位置，条件是在这么多的二进制数中，这两个位置
都为1的次数超过50次。
比如输出：
第1位，第2位
第5位，第20位
.
.
.
请问有什么好的算法吗？ | k**********g
发帖数: 989 | 2
I can think of a two-pass approach.
First pass, Find the digits that do not have enough ones (i.e. bit positions
for which less than 50 inputs have a value of one in that bit position).
This first step is optional - even if you skip this step, you still only
need to accumulate ( 30 * 29 / 2 ) = 435 histogram bins.
// initialize
foreach bitIndex
accum [ bitIndex] = 0
// accumulate
foreach inputIndex
foreach bitIndex
accum [ bitIndex ] += input [ inputIndex ] . bit [ bitIndex ]
// Second step.
Let SelectTwo = ...
... Select ( i , j ) from ( bitIndex.Min <= i < j <= bitIndex.Max )
// initialize
foreach tuple ( i, j ) in SelectTwo
histogram [ i, j ] = 0
// accumulate
foreach inputIndex
foreach tuple ( i, j ) in SelectTwo
if ... ( input [ inputIndex ] . bit [ i ] == 1 ) ,
AND ( input [ inputIndex ] . bit [ j ] == 1 ) ,
then
histogram [ i , j ] += 1
endif
// print result
foreach tuple ( i , j ) in SelectTwo
if histogram [ i , j ] >= 50
print i , j , histogram [ i , j ]
endif
【在 g********o 的大作中提到】
: 假设有300个二进制数 （每个二进制数都是30位）
: 1001001011111011110
: 1010101110111111001
: 1010111101110101110
: 1011111000000010101
: ..
: ..
: ..
: ..
: 1001001011111011110
| f****8
发帖数: 33 | 3 楼上的算法复杂度为O(M^2*N^2).
下面给出O(M*N)的算法，以及实现。
第一步，先扫描各行各列，找出每一列1的个数，然后将每列1的个数及列号按个数从大
到小排列到
一个LIST中，且直接忽略1的个数小于50的列号；O(M*N)+O(MlogM)，其中N为行数，M为
列数。
第二步，根据第一步扫描的结果，创建 FP－tree（Frequency Pattern tree)。创建方
法如下：树中每个节点包括column-index,出现次数，worst复杂度O(M*N).
第三步，统计结果，就是遍历树的过程，有一些技巧，worst复杂度为O(M^2).
因为N》M，所以整体worst复杂度：O(M*N).
本人冬季刚计算机工程专业硕士毕业，之前在国内有一定工作经历，JAVA C++ WEB DB
都做过一些。找湾区码农工作，prefer涉及BIG DATA和MACHINE LEARNING相关的工作，
求内推：f****[email protected]，万分感激！ | m***c
发帖数: 257 | 4 顶干货
N)
【在 f****8 的大作中提到】
: 楼上的算法复杂度为O(M^2*N^2).
: 下面给出O(M*N)的算法，以及实现。
: 第一步，先扫描各行各列，找出每一列1的个数，然后将每列1的个数及列号按个数从大
: 到小排列到
: 一个LIST中，且直接忽略1的个数小于50的列号；O(M*N)+O(MlogM)，其中N为行数，M为
: 列数。
: 第二步，根据第一步扫描的结果，创建 FP－tree（Frequency Pattern tree)。创建方
: 法如下：树中每个节点包括column-index,出现次数，worst复杂度O(M*N).
: 第三步，统计结果，就是遍历树的过程，有一些技巧，worst复杂度为O(M^2).
: 因为N》M，所以整体worst复杂度：O(M*N).
| u****u
发帖数: 229 | 5 写了一个,请大家指正.没有编译过.
void GetPair(void)
{
int32 Data[300];
int index[30];
int i,j;
for (i=0;i<30;i++)
for (j=0;j<30;j++)
index[j]+=(data[i]>>j)&1;
for (i=0;i<30;i++)
for (j=i;j<30;i++)
if (index[i]+index[j]>50)
printf("%d %dn",i,j);
}
【在 g********o 的大作中提到】
: 假设有300个二进制数 （每个二进制数都是30位）
: 1001001011111011110
: 1010101110111111001
: 1010111101110101110
: 1011111000000010101
: ..
: ..
: ..
: ..
: 1001001011111011110
| m****t
发帖数: 2329 | 6 为啥是 int32型
【在 u****u 的大作中提到】
: 写了一个,请大家指正.没有编译过.
: void GetPair(void)
: {
: int32 Data[300];
: int index[30];
: int i,j;
: for (i=0;i<30;i++)
: for (j=0;j<30;j++)
: index[j]+=(data[i]>>j)&1;
: for (i=0;i<30;i++)
|
|
