逆序数
给定一个数组[7,5,6,4]
这个数组的逆序数为5对(7,5) (7,6) (7,4) (5,4) (6,4)
第一种做法
无非是开始两遍循环找到所有的逆序对，设置计数变量，每一次符合条件则加一
逻辑很简单，代码如下
def inversenum(a):
num = 0
for i in range(0,len(a)):
for j in range(i,len(a)):
if a[i] > a[j]:
num += 1
return num
第二种做法
用归并来解决逆序对的问题
就是基本的归并排序然后在归并过程中进行计数
既然是基本的归并排序，那先写一个归并排序的样子出来吧
def merge(a,b):
global count
c = []
i,j = len(a)-1,len(b)-1
num =0
while i >= 0 and j >= 0:
if a[i] > b[j]:
num += j+1
c.insert(0,a[i])
a.pop(i)
i -= 1
else:
c.insert(0,b[j])
b.pop(j)
j -= 1
for each in a:
c.insert(0,each)
for each in b:
c.insert(0,each)
count += num
return c
def sort(a):
if len(a) <= 1:
return a
mid = len(a) /2
left = sort(a[:mid])
right = sort(a[mid:])
return merge(left,right)
这里在写的时候在网上查了一下python查找逆序对的方法
脑子大概是抽掉了，才会说逆序数是3 = =
所以上面应该是insert(0,i)
如果我对逆序数的理解没有错的话，[2,1,4,3]的逆序数应该是3而不是2，
网上查到的这种做法应该是错误的
kendall tau距离
查找数组的逆序数是在一个数组中查找，kendall tau距离是指两个数组之间，一般表示的是两个数组的相似度
example
a = [0,3,1,6,2,5,4]
b = [1,0,3,6,4,2,5]
ab的kendall tau 距离 就是逆序对的个数
(1,0) (3,2) (6,4) (6,2) (6,5) (4,2)
第一种做法
对于b中每一个数，依次遍历这个数后面的数，并与a中所对应数的后面的数进行比对，如果不在则为逆序对，num++
时间复杂度太高了·····
下面是时间复杂度低的做法：
第二种做法
先来考虑一种特殊情况：
当a为顺序自然数数组的时候，b对a的逆序数对即为b自身逆序数对数量
同理，当a的顺序打乱，kendall tau 距离是为b按照a的顺序排列后的逆序数对（解释不太清楚，就是这个意思）
先来实现一下
def kendall_tau(a,b):
#先拿出a的索引
a_index = [0]*len(a)
for i in range(0,len(a)):
a_index[a[i]] = i
#return a_index
b_index = [0]*len(b)
for i in range(0,len(b)):
b_index[i] = a_index[b[i]]
# return b_index
print (b_index)
sort(b_index)
return count
除了取出取出a的索引来排b之外其他都为数组逆序数的算法。b按照a的顺序排列总是一时想的清一时想不清。大抵不过是还未理解吧 🙆
