在Python中查找反演的程序
假设我们已经得到了一个数字列表。我们必须找到现有四元组(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_summodm
在sorted_as的末尾插入nums[b]
对列表进行排序sorted_as
quadruplet_count:=quadruplet_count+as_smaller_than_b_sum*ds_smaller_than_c[b+1]
quadruplet_count:=quadruplet_countmodm
返回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