题解 | 数组中的逆序对
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
from re import I
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def InversePairs(self , nums: List[int]) -> int:
MOD = 1000000007
right_sorted = []
count = 0
for x in reversed(nums):
# 手动二分查找插入位置
lo, hi = 0, len(right_sorted)
while lo < hi:
mid = (lo + hi) // 2
if right_sorted[mid] < x:
lo = mid + 1
else:
hi = mid
pos = lo # 第一个 >= x 的位置
count = (count + pos) % MOD
right_sorted.insert(pos, x)
return count % MOD
查看29道真题和解析