python常见算法面试题（Python解答蚂蚁金服面试的算法题）

前几天看了一个视频，讲的是蚂蚁金服面试的一道算法题，题目是统计给定列表中的逆序数。

在打开思路之前，先介绍一下什么是逆序数。举个简单的例子，一个数组列表为：[5,3,1,1],其中逆序数有(5,3)、(5,1)、(5,1)、(3,1)、(3,1)总计5个。

对逆序数有了了解后，想必有一点python基础的朋友肯定就会想到最简单的一个思路，也是比较暴力的思路。

即用for循环取值，然后一个一个比较大小，设置一个变量，累加起来即可。代码如下，只有几行：

#Written by magiczsd # coding=UTF-8 import time li = [23,1,11,11,1,2,5,1,22] k = 0 #设置一个变量k li_len = len(li) start = time.time() for i in li: #循环取列表里的数值和后面的数值比较大小 k = 1 for j in range(k,li_len): if i > li[j]: #如果为真，则变量加1 num =1 print(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-8 import time li = [23,1,11,11,1,2,5,1,22] num = 0 def 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-8 import time li = [23,1,11,11,1,2,5,1,22] num = 0 def NiXuShu(li): min_value = min(li) #得到列表里的最小值 min_index = li.index(min_value) #最小值在列表的索引值 num = min_index #索引值即为最小值与左边的数值组成的逆序数个数 return num,min_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)

上面的三种思路，第一种比较容易理解，第二种和第三种需要稍微思考下也是比较容易理解的。虽然这三种思路都可以解决问题，不过速度却不一样。在列表里的元素不多的时候，三种代码处理起来看不出差别，当元素达到上千上万甚至更多的时候，第一种处理起来会变得很慢，其次是第二种，速度最快的是第三种思路，有兴趣的朋友可以去测试一下。

代码如写的有所不足，希望大家指出，在python学习的路上一起进步！

代码已上传GitHub（https://github.com/magiczsd/office）