LeetCode 中Global and Local Inversions我覺得是很有趣的一題，這同樣也是屬於看懂了題目之後，就會很好解出答案的一題，相反的如果沒有看懂題目就有可能會花很多時間去寫一個錯誤的寫法，以下會提供兩種寫法，一種是基本的寫法，另一種則是當你完全理解題目之後，能夠寫一個更簡短運行速度也更快的，那就開始進行講解吧！
LeetCode Global and Local Inversions 題目詳解
Global and Local Inversions一樣做中翻英的話，給定一個陣列num長度為n，其元素為隨機排列0~n-1的數字，其中
Global inversions代表存在多少<I , j>對數符合 0<= I < j < n 且 num[I]>num[j]
Local inversions代表存在多少<I >符合ㄢ0 <= I <n-1 且 num[I]>num[I+1]
答案需要判斷上面兩者是否一樣，並回傳布林值，將其在換得直白一點的話，global代表前項大於後項的個數，local則代表前一項大於後一項的個數，一看到這個題目我腦中最直覺的解法就會是，利用雙迴圈去遍歷整個陣列，並且設定條件，只要前項大於後項就將global+1，並在同時判斷其是不是local也就是前項+1是否等於後項，
如果等於的話local+1，整個迴圈結束之後再來判斷global是否等於local，這個是第一個最好想，但寫起來也最複雜且運算時間長的，我們直接來看程式碼！
for i,e_i in enumerate(A):
for j,e_j in enumerate(A):
if i<j:
if e_i>e_j: #A[i]>A[j] 滿足前項大於後項 需要判斷是
sum_global+=1
if i == j-1 : #判斷local條件 也有可能為global
sum_local +=1
if sum_local == sum_global:
return True
else:
return False
這樣就是一個非常簡單的解法，但同時運算時間也會拉得長，開始寫LeetCode之後，我覺得最該養成的習慣就是尋找能夠更省時間的寫法，這也是我認為LeetCode除了面試刷題以外更重要的一點就是培養工程師更好的解決問題的方式，題外話了。
另一種更好的解法
在這個題目中，主要的重點是要讓前項大於後項的狀況只存於鄰近兩項，如果我們仔細思考的話，由於整個陣列是由0~n-1的數字不重複的去填滿陣列，代表會造成這樣的狀況的話
所有項數都只能待在和自己index前後加一的位置
什麼意思呢我們來看個例子，[0,1,2,3,4,5]這是一個完全沒有inversion的例子，這個時候如果我們調換1和4，形成[0,4,2,3,1,5]，肯定會造成global>local的狀況，因為4如果不在陣列index3,5的位置，都一定會大於兩個以上的後項，同理，不管你掉換哪一個數字，只要他不在index前後加一，就代表他後面必須得放超過兩個以上比自己小的數字，再看一個例子，如果2和0進行調換，代表1和0都一定會放在2後面，而這就一定會造成global>local，從這個思路我們可以得到以下的程式碼。
for i in range(len(A)):
if A[i]!=i: #不在自己的位置上
if A[i] == i+1 or A[i] == i-1:#前一個位置或後一個後位置
pass
else:
return False
return True
利用這個思路，單迴圈就可以很好的解決這個問題，並且我們也能更加洞察這個題目，那今天的講解就到這邊！