满足关系的元素数
Number of elements that satisfy a relation
给定两个数组：
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)，太慢了。我知道没有比这更好的最坏情况复杂性了，但我最感兴趣的是平均结果。那么：还有更好的way/algorithm吗？
我想过使用传递属性（如果(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)
我非常喜欢思考这个问题。它确实感觉像是一个 CS 作业问题，所以我会尝试在不解决所有问题的情况下触及概念。
海滩男孩原则
我的微积分老师使用的一个术语，实际上是一种非常适用的解决问题的技巧。基本上，如果你有一个棘手的问题，说 "wouldn't it be nice if..."，看看是否有什么东西可以让事情变得更容易。如果有的话，看看你能不能做到。
在这种情况下，如果顶层数组被排序并且只是 [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
这个的时间复杂度我留给reader一个练习。
P.S。不要忘记撤消映射的时间复杂度。有时您会在解决问题时认为很容易发现构建和解构映射的成本非常高，您必须重新开始。
给定两个数组：
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)，太慢了。我知道没有比这更好的最坏情况复杂性了，但我最感兴趣的是平均结果。那么：还有更好的way/algorithm吗？
我想过使用传递属性（如果(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)
我非常喜欢思考这个问题。它确实感觉像是一个 CS 作业问题，所以我会尝试在不解决所有问题的情况下触及概念。
海滩男孩原则
我的微积分老师使用的一个术语，实际上是一种非常适用的解决问题的技巧。基本上，如果你有一个棘手的问题，说 "wouldn't it be nice if..."，看看是否有什么东西可以让事情变得更容易。如果有的话，看看你能不能做到。
在这种情况下，如果顶层数组被排序并且只是 [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
这个的时间复杂度我留给reader一个练习。
P.S。不要忘记撤消映射的时间复杂度。有时您会在解决问题时认为很容易发现构建和解构映射的成本非常高，您必须重新开始。