c# - 比较数字算法

Question

我正在尝试比较两组数字。我将以随机顺序获得数字。目标是获取第二个列表中的数字，并将它们定位在第一个列表中。这些数字是第一个列表的文件中给出的点列表的 X 坐标，然后由用户通过单击第二个列表的图像来选择。例如 X 坐标集 1:

1. 177
2. 150
3. 212
4. 45
5. 91
6. 330

然后是 X Coord Set 2(不总是 3 个点，可能是 2 个，也可能是 5 个):

1. 212
2. 91
3. 150

这部分很简单，因为您只需比较第二个列表中的哪些与第一个列表中的相同。然而，当点被抵消时它变得更难。例如在下图中，红色的原始图像是默认位置，蓝色是偏移 +20px 的不同图像，这使得 X 点偏移 +20px。我用红色标记了原始图像点，用蓝色标记了用户点击，最后用黑色标记了图像应该是什么样子。

我的问题是，如果存在像图像中那样的图像偏移，找出哪些点被点击的最有效方法是什么。它不会总是 20px，也不会总是正数。也许减去分数并找到最常见的数字？

Answer 1

据我所知，您在每次运行中总是有一个固定的偏移量，但您不知道偏移量是多少，任何贪婪的几何解决方案，例如将最接近的对匹配在一起，都可能导致错误的答案。

对两个列表中的数字进行排序，然后找到一一对应的关系。不管偏移量如何变化，在排序列表中数字总是在正确的位置。要以原始格式检索它，您可以执行以下操作(伪代码):

struct item 
{
int value;
int position;
}

List<item> inputs = new List<item>()
List<item> original = new List<item>()

for i=1 ... n :

original[i] = new item{lst1[i],i}
inputs[i] = new item{lst2[i],i}

Sort inputs and originals w.r.t. their values,

For i=1...n
input[i].position = original[i].position;

For i=1..n
lst2[inputs[i].position] = inputs[i].value;

请注意，上面的伪代码仅在两个列表具有相同大小时才有效，对于它们具有不同大小的情况，我稍后会更新我的答案。

考虑我们有两个不同大小的排序列表:

原始:200 211 222 233 244 255 ..... 299

和

输入:224、257、279

首先我们假设224对应200，那么257应该对应257-24 = 223，但是列表中没有223，将指针向前移动，假设224对应211那么257应该对应257 - 13 = 244，我们原表中有244，那么279应该对应279 - 13 = 256，但是原表中没有256，所以将指针向前移动...，我们可以看到224 -> 244、257->277、279->299。当然，在某些情况下可能会有多个对应关系，但我们无法通过现有信息来区分它们。假设第一个列表的大小为 n，第二个列表的大小为 m，算法运行时间为 O(m.n)，因为通常第二个列表很小(用户点击)，这几乎是线性的。另一方面，找到最长公共(public)子序列是 O(n^2)，因此上述算法相当不错。