# 逆序对数

2019/04/04 20:55

(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；

class Solution:
def InversePairs(self, data):
# write code here
return self.inverseCount(data[:], 0, len(data)-1, data[:])%1000000007

def inverseCount(self, tmp, start, end, data):
if end-start <1:
return 0
if end - start == 1:
if data[start]<=data[end]:
return 0
else:
tmp[start], tmp[end] = data[end], data[start]
return 1
mid = (start+end)//2
cnt = self.inverseCount(data, start, mid, tmp) + self.inverseCount(data, mid+1, end, tmp)
# print(start, mid, end, cnt, data)
i = start
j = mid + 1
ind = start

while(i <= mid and j <= end):
if data[i] <= data[j]:
tmp[ind] = data[i]
i += 1
else:
tmp[ind] = data[j]
cnt += mid - i + 1
j += 1
ind += 1
while(i<=mid):
tmp[ind] = data[i]
i += 1
ind += 1
while(j<=end):
tmp[ind] = data[j]
j += 1
ind += 1
return cnt

class Solution:
def InversePairs(self, data):
count = 0
copy = []
for i in data:
copy.append(i)
copy.sort()
for i in range(len(copy)):
count += data.index(copy[i])
data.remove(copy[i])
return count%1000000007

0
0 收藏

0 评论
0 收藏
0