2

给定两个数组：

2 5 6 4 3 7 1
5 1 6 2 3 7 4

计算两个数组x, y中满足x之前条件的元素个数。y

目前进展：

按索引对数组进行排序。例如，这将是：

                     object: 1 2 3 4 5 6 7
indexes in the first array:  6 0 4 3 1 2 5
indexes in the secnod array: 1 3 4 6 0 2 5

并将每个元组与另一个元组进行比较。如果元组a的两个索引都低于或高于 tuple b，则增加满足条件的元素数。

这有(N^2)/2的时间复杂度，所以O(N^2)，太慢了。我知道没有更好的最坏情况复杂性，但我最感兴趣的是平均结果。那么：有没有更好的方法/算法？

我想过使用传递属性（如果两者都(x,y)满足(y,z)条件，那么(x,z)也满足它），但没有运气。

测试用例

对于数组：

2 5 6 4 3 7 1
5 1 6 2 3 7 4

满足条件的对是：

(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7)

对于数组：

1 2 3 4 5 6 7
1 2 3 4 5 6 7

满足条件的对是：

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7)
4

1 回答 1

1

我非常喜欢思考这个问题。它确实感觉像是一道 CS 作业题，所以我会尝试在不解决所有问题的情况下触及这些概念。

海滩男孩原则

我的微积分老师使用的一个术语，实际上是一种非常适用的问题解决技术。基本上，如果您有一个棘手的问题，请说“如果...不是很好”，然后看看是否有什么可以使事情变得更容易。如果有，看看你能不能做到。

在这种情况下，如果顶部数组是有序的，那不是很好[1, 2, 3 ...]吗？这将使解决这个问题变得更加容易，因为它将两个数组问题变成了一个数组问题。

嗯，可以这样！您可以将这些问题中的任何一个映射到具有有序第一个数组的问题中。

您列出的第一个示例：

2 5 6 4 3 7 1
5 1 6 2 3 7 4

我认为上面的问题等同于下面的问题：

1 2 3 4 5 6 7
2 7 3 1 5 6 4

映射

我只是做一个简单的密码替换 2->1 5->2 6->3 4->4 3->5 7->6 1->7 （为什么这个特殊的映射？）。这使问题的基本结构保持不变。然后，您可以解决此问题，然后撤消映射。

您会发现这种将一个问题映射为更简单问题的技术经常出现在计算机科学中，尤其是在您的算法和可计算性类中。

您现在有一个数组问题来查找所有对：

2 7 3 1 5 6 4

我给读者留了一个练习的时间复杂度。

PS不要忘记撤消映射的时间复杂度。有时你会解决一个问题，认为很容易发现构建和解构你的映射非常昂贵，你必须回到绘图板上。

于 2016-10-09T20:19:24.407 回答