一个面试题

yacare

每个数字均可用二进制形式表示，例如：32可表示为100000, 48可表示为110000, 12可表示为1100, 3可表示为11 ...。
如果一个数a的二进制表示完全位于另一个数b的二进制表示中的首位，则b被a covered， a covers b。例如48被12和3 covered。

现有n个数，n<2**m，这些数字都是唯一的。需要记录每个数字所cover的数字的集合，例如目前的数字是{32,48,12,3}，则3的cover集合是[3,12,48]。现需要完成下列操作。

1）新增一个数a，输出所有变化了的现有数中的cover集合。例如{32,48,12,3}中增加了24 (11000)，则输出应为 24: [24, 48]， 12: [12, 24, 48], 3: [3,12,24,48]。
2）删除一个数a，输出所有变化了的现有数中的cover集合。例如{32,48,12,3}中增加了删除了12 (1100)，则输出应为 3: [3, 48]。

请设计一个需要存储空间最小的算法和一个速度最快算法，并分析它的空间、时间复杂度。

一个我能想到的简单方法是利用binary tree，每个节点用不同的颜色表示其存在或不存在，这样生成一个给定数字的cover集合是O(m)+O(2**m)。O(m)是定位给定数字所需要的操作， 而O(2**m)是寻找一个节点所有存在的children所需要的操作。但这个算法存储空间不小，因为你可能需要存储许多并不存在的节点。 而且时间复杂度也不小。。。。

ypxing

需要空间最小的话，方法可能较多，但要注意，有许多不要重复存储的，比如12: [12, 24, 48], 3: [3,12,24,48]
只存一个最长的，会省很多空间。
对于这例子{32,48,12,3}，也可以考虑，所有数据用链表串起来，对于有cover关系的用另外的双向指针连接
感觉空间O(n)可以搞定的

需要速度最快的话，则用数组存储，数m放在m-1的位置，则访问就很快了

原帖由 yacare 于 2007-7-12 01:29 发表
每个数字均可用二进制形式表示，例如：32可表示为100000, 48可表示为110000, 12可表示为1100, 3可表示为11 ...。
如果一个数a的二进制表示完全位于另一个数b的二进制表示中的首位，则b被a covered， a covers  ...

[ 本帖最后由 ypxing 于 2007-7-12 08:22 编辑 ]

yacare

面试的人说最大的数字可能是2^128，所以不大可能用数组来存储。

原帖由 ypxing 于 2007-7-12 08:04 发表
需要空间最小的话，方法可能较多，但要注意，有许多不要重复存储的，比如12: [12, 24, 48], 3: [3,12,24,48]
只存一个最长的，会省很多空间。
对于这例子{32,48,12,3}，也可以考虑，所有数据用链表串起来，对 ...

jigloo

并查集

runforu

直接右移操作就可以了。右移一位后与其他数字比较，bitset好像可以。