您如何将一组充满 "holes" 的数字映射到没有 "holes" 的较小数字
How can you map a set of numbers, full of "holes" into a smaller one without "holes"
任何人都可以想出一个函数来从 N 个数字的有限集合 X = {x0, x1, x2, ..., xN} 中执行映射，其中每个 x 的值可以是 0 到 999999999 并且 N < 999999999，到集合 Y = {0, 1, 2, 3, ..., N}.
就我而言，我在第一组中有大约 24000000 个元素，其值范围为 X。这些元素具有连续块（例如 53000 到 1234500，然后是 8000000 到 9000000 等等），我必须重新映射这个元素从 0 到 2400000。我不需要维持秩序。
我需要一个（可能简单快速的）数学函数，或者一个按位转换，而不是像把它排序到一个数组中然后二进制搜索它们的位置。
真是感谢哪位能想出办法解决这个问题！
卢卡
如果您不想保留 几千兆字节 的直图，那么扩充线段树是合理的方法。树应该包含间隔和每个间隔的移位（左间隔的总和）。当然，在这种方法中找到合适的区间（和移位）接近二分查找。
例如，您得到 X=80000015。查找此值的间隔 - 它是 8000000 to 9000000。这个区间的排名是 175501 (1234500-53000 + 1)。所以 X 映射到
X => 175501 + 80000015 - 80000000 = 175516
对于稀疏元素进行计数阶段 - 找到每个数字 M 的秩 R，并将 (key=M, value=R) 对放入哈希 table。
X = (3, 19, 20, 101)
table: [(3:0), (19:1), (20:2), (101:3)]
请注意，应该在速度和 space 之间保持平衡 - 对于较长的填充间隔，最好只存储间隔结束。
任何人都可以想出一个函数来从 N 个数字的有限集合 X = {x0, x1, x2, ..., xN} 中执行映射，其中每个 x 的值可以是 0 到 999999999 并且 N < 999999999，到集合 Y = {0, 1, 2, 3, ..., N}.
就我而言，我在第一组中有大约 24000000 个元素，其值范围为 X。这些元素具有连续块（例如 53000 到 1234500，然后是 8000000 到 9000000 等等），我必须重新映射这个元素从 0 到 2400000。我不需要维持秩序。
我需要一个（可能简单快速的）数学函数，或者一个按位转换，而不是像把它排序到一个数组中然后二进制搜索它们的位置。
真是感谢哪位能想出办法解决这个问题！ 卢卡
如果您不想保留 几千兆字节 的直图，那么扩充线段树是合理的方法。树应该包含间隔和每个间隔的移位（左间隔的总和）。当然，在这种方法中找到合适的区间（和移位）接近二分查找。
例如，您得到 X=80000015。查找此值的间隔 - 它是 8000000 to 9000000。这个区间的排名是 175501 (1234500-53000 + 1)。所以 X 映射到
X => 175501 + 80000015 - 80000000 = 175516
对于稀疏元素进行计数阶段 - 找到每个数字 M 的秩 R，并将 (key=M, value=R) 对放入哈希 table。
X = (3, 19, 20, 101)
table: [(3:0), (19:1), (20:2), (101:3)]
请注意，应该在速度和 space 之间保持平衡 - 对于较长的填充间隔，最好只存储间隔结束。