w********s
发帖数: 1570 | 1 一组int流，范围0-100，比如3,1,4,6,8,7...
要求返回小于i的数字个数,s(i)
简单的做法就是开一个0-100的数组，来一个数字j，就a[0]-a[j]++
有没有快一点的办法？ | f*****e
发帖数: 2992 | 2 binary index tree
【在 w********s 的大作中提到】
: 一组int流，范围0-100，比如3,1,4,6,8,7...
: 要求返回小于i的数字个数,s(i)
: 简单的做法就是开一个0-100的数组，来一个数字j，就a[0]-a[j]++
: 有没有快一点的办法？
| c*******7
发帖数: 438 | 3 开一个size为101的数组，来一个数字j，就a[j]++。所有数字扫完后，过一遍数组，a[
i+1] =a[i]+a[i+1]。
【在 w********s 的大作中提到】
: 一组int流，范围0-100，比如3,1,4,6,8,7...
: 要求返回小于i的数字个数,s(i)
: 简单的做法就是开一个0-100的数组，来一个数字j，就a[0]-a[j]++
: 有没有快一点的办法？
| v*****y
发帖数: 68 | 4 CC 150有类似的，用BST存，每个node存i和左子树的数量 | w*******e
发帖数: 395 | 5 这个怎么讲？详细点？
【在 v*****y 的大作中提到】
: CC 150有类似的，用BST存，每个node存i和左子树的数量
| g*********e
发帖数: 14401 | 6 cc150那个解法不能保证平衡树，算法导论里有基于r b tree的类似解法
【在 v*****y 的大作中提到】
: CC 150有类似的，用BST存，每个node存i和左子树的数量
| v*****y
发帖数: 68 | 7
对于每个Node,需要存储i，range (number of left nodes in left subtree),left,
right
如果新的node插进来，如果这个node的位置在node1的左子树，需要更新node1的range。
楼上也提到了，这个方法不能保证树的平衡，在构造树的时候，可以使用其他方法保证
他的平衡性。
【在 w*******e 的大作中提到】
: 这个怎么讲？详细点？
| F****n
发帖数: 3271 | 8 已经知道范围1-100就不应该用BST
直接用数组就是最好解
BST适合范围未知或已知但很大（如1-1000000000）而实际值分散
【在 f*****e 的大作中提到】
: binary index tree
| r****7
发帖数: 2282 | 9 overkill了，就100个数想建一个balanced tree还不容易
【在 g*********e 的大作中提到】
: cc150那个解法不能保证平衡树，算法导论里有基于r b tree的类似解法
| Y******g
发帖数: 16 | 10 树状数组
http://zh.wikipedia.org/wiki/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%
树状数组支持
1）更行数组中的一个元素
2）求任意连续subarray的和
这两个操作都是O(lnN),N是数组中元素个数。如果只有100个数字，这个就成常数了。 |
|
