algorithm - 如何将非线性范围指向线性范围并返回？

Question

我有一个线性范围列表，代表一个大范围:

                                          X'
 100    200 300    400 500    600 700     |       900    (X)
|----------|----------|----------|--------+----------|
 0                                        |       100    (Y)
                                          Y'

X 由以下范围组成(偶数和整数只是为了便于理解的示例，它们可以是任何东西，这里根本没有比例):

• 从 100 到 200
• 从 300 到 400
• 从 500 到 600
• 从 700 到 900

另一方面，Y 只有一个范围:

• 从 0 到 100

X 和 Y 的长度相同，只是单位不同。假设一个是美元，另一个是百分比(或任何其他类似的无关单位)。所以 Y'0 == X'100 和 Y'100 == X'900。

给定 Y 中的任意点，X 中的等价点是什么，反之亦然，给定 X 中的点 - Y 中的点是什么？

这是一道典型的数学题吗？它有名字吗？

Answer 1

你有多少个范围？算法是 O(范围数)是否可以接受？

如果是这样，下面是算法的描述。让我在您的(原始)示例中解释一下。

 100    200 300    400 500    600 700    800
|----------|----------|----------|----------|
 0%                                     100%

1) 您要做的是将范围 A (100-800) 中的值 X 映射到连续范围 B (0-399) 中的值 Y(因为范围内的元素总数是400)。然后很容易将B中的位置更改为百分比，我将省略这部分。

2) 创建一个记录列表，其中每个记录代表一个范围映射。

struct RangeRecord {
  int start_in_a;
  int start_in_b;
};

在您的情况下，您将获得以下列表:

{100, 0}, {300, 100}, {500, 200}, {700, 300}

3) 当你需要将数字 X 从 A 映射到 B 时，你迭代列表以找到具有 start_in_a <= X 的第一条记录。那么你的值 Y 是

Y = X + start_in_b - start_in_a;

4) 该算法是对称的，您只需迭代列表以找到 start_in_b <= Y 的第一条记录，然后

X = Y + start_in_a - start_in_b.

注意 1. 出于错误检查的目的，您也可以在 RangeRecord 中保留范围大小。

注意 2. 如果 O(number of ranges) 不够好，请将记录保留为树而不是列表。然后你将需要 O(log(number of ranges)) 操作，