求逆序对数量 leetcode

求逆序对的数量是一个经典的计算机科学问题，通常出现在算法竞赛和LeetCode等在线编程平台的面试题中。问题的目标是给定一个整数数组，计算其中有多少对元素满足这样的条件：第一个元素大于第二个元素。

例如，对于数组 [5, 2, 4, 6, 1]，逆序对有 (5, 2), (5, 1), (6, 1) 和 (4, 1)，总共有4对。

解决这个问题的一个常见方法是使用哈希表（也称作HashMap）。我们可以遍历数组，同时将每个元素作为键存储到哈希表中，并将其值初始化为其索引。然后再次遍历数组，对于每个元素，我们从哈希表中查找比它小的元素的数量，这个数量就是当前元素能够构成的逆序对数量。最后，所有元素都能贡献出它们自身的“剩余”位置作为逆序对。

以下是Python的一个简单示例：

def reversePairs(nums):
    count = 0
    map = {num: i for i, num in enumerate(nums)}
    for num in nums:
        if num in map:
            count += len(map) - map[num]
        else:
            count += len(map)
    return count