数满足关系

Question

给定两个数组中的元素：

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的索引低于或高于元组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) 

Answer 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 

这样做的时间复杂度我留下一个练习给读者。

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