假设我们已经得到了一个数字列表。我们必须找到现有四元组(a,b,c,d)的数量，以使a <b <c <d和nums [a] <nums [b]和nums [c]> nums [d]。
数组nums是整数1 ... N的排列
因此，如果输入类似于nums = [3、4、7、6、5]，则输出将为5。
从给定的输入，我们有这些反转的反转-
3、4、7、6
3、4、6、5
3、4、7、5
3、7、6、5
4、7、6、5
为了解决这个问题，我们将遵循以下步骤-
m：= 10 ^ 9 + 7
如果nums <4
返回0
n：= nums的大小
sorted_ds：=一个新列表
在sorted_ds中插入nums的最后一项
对列表进行排序sorted_ds
ds_smaller_than_c：= [0] * n
对于范围为n − 2至-1的c，减1，
ds_smaller_than_c [c]：=返回sorted_ds中最右边的位置，可以插入nums [c]-1并保持排序顺序
在sorted_ds的末尾插入nums [c]
对列表进行排序sorted_ds
quadruplet_count：= 0
sorted_as：=一个新列表
在sorted_as中插入第一个数字
对列表进行排序sorted_as
as_smaller_than_b_sum：= 0
对于b在1到n − 2的范围内，执行
as_smaller_than_b_sum：= as_smaller_than_b_sum + sorted_as中最右边的位置，可以插入nums [b] – 1并保持排序顺序
对列表进行排序sorted_as
as_smaller_than_b_sum：= as_smaller_than_b_sum mod m
在sorted_as的末尾插入nums [b]
对列表进行排序sorted_as
quadruplet_count：= quadruplet_count + as_smaller_than_b_sum * ds_smaller_than_c [b + 1]
quadruplet_count：= quadruplet_count mod m
返回quadruplet_count
让我们看下面的实现以更好地理解-
import bisect MOD = 10 ** 9 + 7 class Solution: def solve(self, nums): if len(nums) < 4: return 0 n = len(nums) sorted_ds = list([nums[−1]]) sorted_ds.sort() ds_smaller_than_c = [0] * n for c in range(n − 2, −1, −1): ds_smaller_than_c[c] = bisect.bisect_right(sorted_ds, nums[c] − 1) sorted_ds.append(nums[c]) sorted_ds.sort() quadruplet_count = 0 sorted_as = list([nums[0]]) sorted_as.sort() as_smaller_than_b_sum = 0 for b in range(1, n − 2): as_smaller_than_b_sum += bisect.bisect_right(sorted_as, nums[b] − 1) sorted_as.sort() as_smaller_than_b_sum %= MOD sorted_as.append(nums[b]) sorted_as.sort() quadruplet_count += as_smaller_than_b_sum * ds_smaller_than_c[b + 1] quadruplet_count %= MOD return quadruplet_count ob = Solution() print(ob.solve([3, 4, 7, 6, 5]))
[3, 4, 7, 6, 5]输出结果
5