前几天看了一个视频，讲的是蚂蚁金服面试的一道算法题，题目是统计给定列表中的逆序数。在打开思路之前，先介绍一下什么是逆序数。对逆序数有了了解后，想必有一点python基础的朋友肯定就会想到最简单的一个思路，也是比较暴力的思路。虽然这三种思路都可以解决问题，不过速度却不一样。代码如写的有所不足，希望大家指出，在python学习的路上一起进步！
前几天看了一个视频，讲的是蚂蚁金服面试的一道算法题，题目是统计给定列表中的逆序数。
在打开思路之前，先介绍一下什么是逆序数。举个简单的例子，一个数组列表为：[5,3,1,1],其中逆序数有(5,3)、(5,1)、(5,1)、(3,1)、(3,1)总计5个。
对逆序数有了了解后，想必有一点python基础的朋友肯定就会想到最简单的一个思路，也是比较暴力的思路。
思路一：遍历统计法。即用for循环取值，然后一个一个比较大小，设置一个变量，累加起来即可。代码如下，只有几行：
#Written by magiczsd# coding=UTF-8import timeli = [23,1,11,11,1,2,5,1,22]k = 0#设置一个变量kli_len = len(li)start = time.time()for i in li:#循环取列表里的数值和后面的数值比较大小k= 1for j in range(k,li_len):if i > li[j]:#如果为真，则变量加1num=1print(num)end = time.time()print(end-start)
思路一比较简单，大家也比较容易理解，但是既然这是蚂蚁金服面试的算法题，考官必定想看到能让眼睛一亮的思路，于是小编思考了下，想到了第二个思路。
思路二：最大值统计法。即先用max函数查找出列表里最大的数值max_value，再用index函数查找最大值在列表里的第一个索引值max_index，接着再用count函数计算出列表里有几个最大值max_counts，最后用len函数计算列表里元素的个数len_num。
将max_index 1便得到这个最大值在列表中是第几个元素（注意：这里需要从1开始计算），用len统计的len_num-（max_index 1）便得到最大值右边的元素个数，最后再减去剩余的最大值个数即max_counts-1，这样便可以得到以这个最大值组成的逆序数个数。
然后用remove函数将这个最大值从列表里剔除，继续重复上面的步骤即可，代码如下：
#Written by magiczsd# coding=UTF-8import timeli = [23,1,11,11,1,2,5,1,22]num = 0def NiXuShu(li):len_num = len(li)#列表的元素个数max_value = max(li)#得到最大值max_index = li.index(max_value)#得到最大值在列表里的第一个位置的索引值max_counts = li.count(max_value)#统计列表里最大值的个数num = len_num - (max_index 1) - (max_counts-1)return num,max_value#返回以这个最大值组成的逆序数的个数和最大值start = time.time()while len(li) != 0:#循环处理，直到列表里最后一个最大值被剔除后，循环结束num= NiXuShu(li)[0]li.remove(NiXuShu(li)[1])#剔除第一个最大值print(num)end = time.time()print(end-start)
当时写完这段代码的时候，小编忽然灵光一闪，既然有最大值统计法，是否也可以有最小值统计法？于是很快最小值统计法的思路便有了。
思路三：最小值统计法。先用min函数查找出列表里的最小值min_value，再用index查找出最小值在列表里的第一个索引值min_index，而这个min_index数值就是这个最小值与它左边的数值组成的逆序数的个数。
比如列表[3,2,1,4]，最小值为1，与1组成的逆序数只有(3,1)、(2,1)数量是2，而其索引值也是2。
有了这样的思路，接下来的统计方法就和思路三的类似了，代码如下：
#Written by magiczsd# coding=UTF-8import timeli = [23,1,11,11,1,2,5,1,22]num = 0def NiXuShu(li):min_value = min(li)#得到列表里的最小值min_index = li.index(min_value)#最小值在列表的索引值num = min_index#索引值即为最小值与左边的数值组成的逆序数个数return num,min_valuestart = time.time()while len(li) != 0:#循环处理，直到列表里最后一个最小值被剔除后，循环结束num= NiXuShu(li)[0]li.remove(NiXuShu(li)[1])#剔除第一个最小值print(num)end = time.time()print(end-start)
上面的三种思路，第一种比较容易理解，第二种和第三种需要稍微思考下也是比较容易理解的。虽然这三种思路都可以解决问题，不过速度却不一样。在列表里的元素不多的时候，三种代码处理起来看不出差别，当元素达到上千上万甚至更多的时候，第一种处理起来会变得很慢，其次是第二种，速度最快的是第三种思路，有兴趣的朋友可以去测试一下。
代码如写的有所不足，希望大家指出，在python学习的路上一起进步！
代码已上传GitHub（https://github.com/magiczsd/office）
