導讀前幾天看了一個視頻，講的是螞蟻金服面試的一道算法題，題目是統計給定列表中的逆序數。在打開思路之前，先介紹一下什么是逆序數。舉個簡單的例子，一個數組列表為：[....

前幾天看了一個視頻，講的是螞蟻金服面試的一道算法題，題目是統計給定列表中的逆序數。

在打開思路之前，先介紹一下什么是逆序數。舉個簡單的例子，一個數組列表為：[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 = 1 for j in range(k,li_len): if i > li[j]: #如果為真，則變量加1 num =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）