这是一种数据结构，可以非常有效地执行所有操作：我将在本说明中称之为
BitmapArray 。考虑到你所描述的操作，一个带有位图作为键和权重（双精度浮点数）作为值的排序数组将非常有效。位图用于维护集合中的成员资格。由于您说集合中的整数范围在1-10,000之间，因此我们可以使用长度为10,000的位图来维护有关任何集合的信息。尽管键可以达到2 ^ 10000那么大，但您可以通过以下方式聪明地实现比较函数来进行排序：从左到右迭代两个位图，在每个索引上XOR位，假设您在第i个位置得到1，具有1的位图更大，如果您从未得到1，则它们相等。
我知道这个比较还是有些慢。
但并不是太慢，这里有一个我在长度为10000的位图上做的基准测试。
这是用Javascript编写的，如果你要用Java编写，它会表现得更好。
function runTest() {
var num = document.getElementById("txtValue").value;
num = isNaN(num * 1) ? 0 : num * 1;
bitmap1 = convertToBitmap(10000, num);
bitmap2 = convertToBitmap(10000, num);
before = new Date().getMilliseconds();
var result = firstIsGreater(bitmap1, bitmap2, 10000);
after = new Date().getMilliseconds();
alert(result + " in time: " + (after-before) + " ms");
}
function convertToBitmap(size, number) {
var bits = new Array();
var q = number;
do {
bits.push(q % 2);
q = Math.floor(q / 2);
} while (q > 0);
xbitArray = new Array();
for (var i = 0; i < size; i++) {
xbitArray.push(0);
}
var j = xbitArray.length - 1;
for (var i = bits.length - 1; i >= 0; i--) {
xbitArray[j] = bits[i];
j--
}
return xbitArray;
}
function firstIsGreater(bitArray1, bitArray2, lengthOfArrays) {
for (var i = 0; i < lengthOfArrays; i++) {
if (bitArray1[i] ^ bitArray2[i]) {
if (bitArray1[i]) return true;
else return false;
}
}
return false;
}
document.getElementById("btnTest").onclick = function (e) {
runTest();
};
此外，请记住，您只需要在构建BitmapArray（或合并时）执行一次此操作，然后对于您经常执行的操作，它将变得非常高效：
注意：N是BitmapArray的长度。
为每个设置添加整数：最坏/最佳情况下为O（N）时间。在每个位图中将0翻转为1。
删除包含给定整数的所有集的最坏情况是O（N）时间。
对于每个位图，请检查表示给定整数的位，如果为1，则标记其索引。
通过删除所有标记的索引来压缩数组。
如果您只想将权重设置为0，那么它将更加高效。如果您想删除具有给定集合中任何元素的所有集，则这也使得它非常容易。
两个地图的联合：最坏情况下为O（N1 + N2）时间。就像合并两个排序数组一样，除了您必须再次聪明比较。
将所有双倍乘以给定的双倍：最坏/最佳情况下为O（N）时间。迭代并将每个值乘以输入双倍。
迭代 BitmapArray：下一个元素的最坏/最优时间复杂度为 O(1)。
Map<Set<int>, double>，你可能想考虑只是继承Set<int>并添加一个Weight字段。 - Andy Jones