《劍指 Offer》（第 2 版）第 51 題：數(shù)組中的逆序?qū)?/h2>
要求：在數(shù)組中的兩個(gè)數(shù)字如果前面一個(gè)數(shù)字大于后面的數(shù)字汰规，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α?/p>
輸入一個(gè)數(shù)組访圃，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)姨裸。
樣例：
輸入：[1,2,3,4,5,6,0]
輸出：6
思路1：使用定義
挨個(gè)數(shù)出來(lái)悲敷，使用定義計(jì)算逆序數(shù)覆履。不過(guò)時(shí)間復(fù)雜度是 蹋盆。
class Solution(object):
def inversePairs(self, nums):
l = len(nums)
if l < 2:
return 0
res = 0
for i in range(0, l - 1):
for j in range(i + 1, l):
if nums[i] > nums[j]:
res += 1
return res
這種思路雖然很直接费薄，但編寫出錯(cuò)的概率很低，在沒(méi)有在線評(píng)測(cè)系統(tǒng)的時(shí)候栖雾，它可以作為一個(gè)“正確的”參考答案楞抡，用以檢驗(yàn)我們自己編寫的算法是否正確。
思路2：分治
這道題最經(jīng)典的思路是使用分治法計(jì)算析藕，借助“歸并排序”的分治思想召廷，排好序以后，逆序?qū)颓蟪鰜?lái)了账胧，時(shí)間復(fù)雜度為 竞慢。下面舉例說(shuō)明：例如：前有序數(shù)組：
，后有序數(shù)組：
治泥。
做歸并的時(shí)候筹煮，步驟如下：
第 1 步， 先出列居夹，
比“后有序數(shù)組”中所有的元素都小败潦，構(gòu)成“順序?qū)Α保?/p>
第 2 步， 出列准脂，
比“后有序數(shù)組”中所有的元素都小劫扒，構(gòu)成“順序?qū)Α保?/p>
第 3 步， 出列狸膏，關(guān)鍵的地方在這里沟饥，“前有序數(shù)組”中所有剩下的元素
比
都大，構(gòu)成
個(gè) “逆序?qū)Α?/strong>环戈；
第 4 步闷板， 出列，
比“后有序數(shù)組”中所有剩下的元素都小院塞，構(gòu)成“順序?qū)Α保?/p>
第 5 步遮晚， 出列，“前有序數(shù)組”中所有剩下的元素
比
都大拦止，構(gòu)成
個(gè)“逆序?qū)Α?/strong>县遣；
第 6 步， 出列汹族，“前有序數(shù)組”中所有剩下的元素
比
都大萧求，構(gòu)成
個(gè)“逆序?qū)Α?/strong>；
第 7 步顶瞒， 出列夸政，
比“后有序數(shù)組”中所有剩下的元素
都小，構(gòu)成
個(gè)“順序?qū)Α保?/p>
第 8 步榴徐， 出列守问，此時(shí)“前有序數(shù)組”為空匀归。
因此，我們只需要在“前有序數(shù)組”非空耗帕，且“后有序數(shù)組”中有元素出列的時(shí)候穆端，即上面的第 3、5仿便、6 步計(jì)算“逆序?qū)Α本涂梢粤恕?/p>
Python 代碼：
class Solution(object):
def inversePairs1(self, nums):
l = len(nums)
if l < 2:
return 0
res = 0
for i in range(0, l - 1):
for j in range(i + 1, l):
if nums[i] > nums[j]:
res += 1
return res
def inversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l < 2:
return 0
temp = [0 for _ in range(l)]
return self.count_inversion_pairs(nums, 0, l - 1, temp)
def count_inversion_pairs(self, nums, l, r, temp):
"""
在數(shù)組 nums 的區(qū)間 [l,r] 統(tǒng)計(jì)逆序?qū)? :param nums:
:param l: 待統(tǒng)計(jì)數(shù)組的左邊界体啰，可以取到
:param r: 待統(tǒng)計(jì)數(shù)組的右邊界，可以取到
:param temp:
:return:
"""
# 極端情況下嗽仪，就是只有 1 個(gè)元素的時(shí)候
if l == r:
return 0
mid = l + (r - l) // 2
left_pairs = self.count_inversion_pairs(nums, l, mid, temp)
right_pairs = self.count_inversion_pairs(nums, mid + 1, r, temp)
merge_pairs = 0
# 代碼走到這里的時(shí)候荒勇，
# [l, mid] 已經(jīng)完成了排序并且計(jì)算好逆序?qū)? # [mid + 1, r] 已經(jīng)完成了排序并且計(jì)算好逆序?qū)? # 如果 nums[mid] <= nums[mid + 1]，此時(shí)就不存在逆序?qū)? # 當(dāng) nums[mid] > nums[mid + 1] 的時(shí)候闻坚，就要繼續(xù)計(jì)算逆序?qū)? if nums[mid] > nums[mid + 1]:
# 在歸并的過(guò)程中計(jì)算逆序?qū)? merge_pairs = self.merge_and_count(nums, l, mid, r, temp)
# 走到這里有 nums[mid] <= nums[mid + 1] 成立枕屉，已經(jīng)是順序結(jié)構(gòu)
return left_pairs + right_pairs + merge_pairs
def merge_and_count(self, nums, l, mid, r, temp):
"""
前：[2,3,5,8]，后：[4,6,7,12]
我們只需要在后面數(shù)組元素出列的時(shí)候鲤氢，數(shù)一數(shù)前面這個(gè)數(shù)組還剩下多少個(gè)數(shù)字，
因?yàn)?前"數(shù)組和"后"數(shù)組都有序西潘，
因此卷玉，"前"數(shù)組剩下的元素個(gè)數(shù) mid - i + 1 就是與"后"數(shù)組元素出列的這個(gè)元素構(gòu)成的逆序?qū)€(gè)數(shù)
"""
for i in range(l, r + 1):
temp[i] = nums[i]
i = l
j = mid + 1
res = 0
for k in range(l, r + 1):
if i > mid:
nums[k] = temp[j]
j += 1
elif j > r:
nums[k] = temp[i]
i += 1
elif temp[i] <= temp[j]:
# 不統(tǒng)計(jì)逆序?qū)Γ蛔雠判? nums[k] = temp[i]
i += 1
else:
assert temp[i] > temp[j]
nums[k] = temp[j]
j += 1
# 快就快在這里喷市，一次可以數(shù)出一個(gè)區(qū)間的個(gè)數(shù)的逆序?qū)? # 例：[7,8,9][4,6,9]相种，4 與 7 以及 7 前面所有的數(shù)都構(gòu)成逆序?qū)? res += (mid - i + 1)
return res
說(shuō)明：歸并兩個(gè)有序數(shù)組的時(shí)候，我們要借助額外的輔助空間品姓，為此可以全局使用一個(gè)和原始數(shù)組等長(zhǎng)的輔助數(shù)組寝并，否則每一次進(jìn)入 merge 函數(shù)都要 new 新數(shù)組，開(kāi)銷很大腹备。
上述解法的缺點(diǎn)是修改了原始數(shù)組衬潦，排序完成以后，逆序數(shù)就計(jì)算出來(lái)了植酥。為此：（1）我們可以引入一個(gè)索引數(shù)組镀岛；（2）或者直接拷貝一個(gè)原始數(shù)組，這樣就不用修改原始數(shù)組了友驮。
思路3：使用“樹(shù)狀數(shù)組”
關(guān)于樹(shù)狀數(shù)組漂羊，我寫了一篇文章，在這里卸留，體會(huì)什么是“離散化”走越。
class Solution(object):
def inversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
class FenwickTree:
def __init__(self, n):
self.size = n
self.tree = [0 for _ in range(n + 1)]
def __lowbit(self, index):
return index & (-index)
# 單點(diǎn)更新：從下到上，最多到 size耻瑟，可以取等
def update(self, index, delta):
while index <= self.size:
self.tree[index] += delta
index += self.__lowbit(index)
# 區(qū)間查詢：從上到下旨指，最少到 1赏酥，可以取等
def query(self, index):
res = 0
while index > 0:
res += self.tree[index]
index -= self.__lowbit(index)
return res
# 特判
l = len(nums)
if l < 2:
return 0
# 原始數(shù)組去除重復(fù)以后從小到大排序
s = list(set(nums))
# 構(gòu)建最小堆，因?yàn)閺男〉酱笠粋€(gè)一個(gè)拿出來(lái)淤毛，用堆比較合適
import heapq
heapq.heapify(s)
# 由數(shù)字查排名
rank_map = dict()
index = 1
# 不重復(fù)數(shù)字的個(gè)數(shù)
size = len(s)
for _ in range(size):
num = heapq.heappop(s)
rank_map[num] = index
index += 1
res = 0
# 樹(shù)狀數(shù)組只要不重復(fù)數(shù)字個(gè)數(shù)這么多空間就夠了
ft = FenwickTree(size)
# 從后向前看今缚，拿出一個(gè)數(shù)字來(lái)，就更新一下低淡，然后向前查詢比它小的個(gè)數(shù)
for i in range(l - 1, -1, -1):
rank = rank_map[nums[i]]
ft.update(rank, 1)
res += ft.query(rank - 1)
return res
說(shuō)明：中間將數(shù)字映射到排名是將原數(shù)組“離散化”姓言，“離散化”的原因有 2 點(diǎn)：
1、樹(shù)狀數(shù)組我們看到蔗蹋，索引是從“”開(kāi)始的何荚，我們不能保證我們的數(shù)組所有的元素都大于等于
；
2猪杭、即使元素都大于等于“”餐塘，為了節(jié)約樹(shù)狀數(shù)組的空間，我們將之“離散化”可以把原始的數(shù)都?jí)嚎s到一個(gè)小區(qū)間皂吮。我說(shuō)的有點(diǎn)不太清楚戒傻，這一點(diǎn)可以參考 樹(shù)狀數(shù)組 求逆序數(shù) poj 2299。
LeetCode 第 315 題：計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)
傳送門：315. 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)蜂筹。
給定一個(gè)整數(shù)數(shù)組 nums需纳，按要求返回一個(gè)新數(shù)組 counts。數(shù)組 counts 有該性質(zhì)：
counts[i]的值是nums[i]右側(cè)小于nums[i]的元素的數(shù)量艺挪。示例:
輸入: [5,2,6,1] 輸出: [2,1,1,0] 解釋: 5 的右側(cè)有 2 個(gè)更小的元素 (2 和 1). 2 的右側(cè)僅有 1 個(gè)更小的元素 (1). 6 的右側(cè)有 1 個(gè)更小的元素 (1). 1 的右側(cè)有 0 個(gè)更小的元素.
解法1：自定義 BST 的解法不翩，比較巧妙，參考：
https://segmentfault.com/a/1190000008233819
【算法】逆序?qū)?wèn)題的四種解法（歸并排序麻裳，BST口蝠，樹(shù)狀數(shù)組，線段樹(shù)）及變形
https://blog.csdn.net/haolexiao/article/details/54989306
leetcode 315 Count of Smaller Numbers After Self 以及 BST總結(jié)津坑。
https://segmentfault.com/a/1190000008233783
Python 代碼：
class Solution:
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
class TreeNode:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
self.left_node_sum = 0
self.duplicate_times = 1
def insert(node, val, index, cum_left_nodeSum, counter):
if node is None:
node = TreeNode(val)
counter[index] = cum_left_nodeSum
return node
if node.val == val:
node.duplicate_times += 1
counter[index] = cum_left_nodeSum + node.left_node_sum
elif node.val > val:
node.left_node_sum += 1
node.left = insert(node.left, val, index, cum_left_nodeSum, counter)
else:
node.right = insert(node.right, val, index,
cum_left_nodeSum + node.duplicate_times + node.left_node_sum, counter)
return node
l = len(nums)
if l == 0:
return []
if l == 1:
return [0]
# 從后向前填表
res = [None for _ in range(l)]
root = None
for index in range(l - 1, -1, -1):
root = insert(root, nums[index], index, 0, res)
print(root)
return res
樹(shù)狀數(shù)組 求逆序數(shù) poj 2299
https://blog.csdn.net/u013445530/article/details/39829053
把離散化搞清楚
poj 2299 Ultra-QuickSort 求逆序數(shù)妙蔗，樹(shù)狀數(shù)組解法，詳細(xì)解析
https://blog.csdn.net/Lionel_D/article/details/43535741
白話數(shù)據(jù)結(jié)構(gòu)
https://blog.csdn.net/column/details/acxxz.html
（本節(jié)完）
