資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：計算給定陣列中大小為三的反轉次數
反轉計數是一種步數計數方法，我們可以用它來計算特定陣列排序所需要的步數。它也可以用來計算陣列的操作時間跨度。但是，如果我們想要以相反的方式對陣列進行排序，則計數將是該陣列中存在的最大數字。
Array: { 5, 4, 3, 2, 1} // for the reverse manner
Pairs: {5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10
Array: {1, 2, 3, 4, 5} // for the increasing manner
Pairs: No Pairs
Output: 0
Array: {1,5,2,8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5
反轉計數表明特定陣列距離按升序排序還有多遠。這裡有兩種特定的過程來描述這種情況以及相應的解決方案：
查詢較小的元素：要從陣列中找出較小的元素，我們需要從n-1到0迭代索引。透過應用(a[i]-1)，我們可以在此處計算getSum()。此過程將一直執行到a[i]-1。
查詢較大的數字：要從索引中查詢較大的數字，我們需要執行從0到n-1的迭代。對於每個元素，我們需要對每個數字進行計算，直到a[i]。從i中減去它。然後我們將得到一個大於a[i]的數字。
陣列中大小為三的反轉計數演算法
在此演算法中，我們將學習如何在特定的程式設計環境中計算給定陣列中大小為三的反轉次數。
步驟1 - 開始
步驟2 - 宣告一個數組和反轉計數（如arr[] --> 陣列和invCount --> 反轉計數）
步驟3 - 內部迴圈y=x+1到N
步驟4 - 如果x處的元素大於y索引處的元素
步驟5 - 然後，增加invCount++
步驟6 - 列印對
步驟7 - 終止
陣列中大小為三的反轉計數語法：
如果滿足以下條件，則一對 (A[i], A[j]) 被稱為反轉：A[i] > A[j] 且 i < j
C++ 實現
int getInversions(int * A, int n) {
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (A[i] > a[j]) {
++count;
}
}
}
return count;
}
Java 實現
public static int getInversions(int[] A, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (A[i] > A[j]) {
count += 1;
}
}
}
return count;
}
Python 實現
def getInversions(A, n): count = 0 for i in range(n): for j in range(i + 1, n): if A[i] > A[j]: count += 1 return count;
這裡我們提到了在給定陣列中計算大小為三的反轉次數的可能語法。對於此方法，時間複雜度為 O(N^2)，其中 N 是陣列的總大小；空間複雜度為 O(1)，因為沒有使用額外的空間。
遵循的方法
方法1 - 透過程式計算給定陣列中大小為三的反轉次數來計算給定陣列中大小為三的反轉次數
方法2 - 計算大小為3的反轉的更好方法
方法3 - 使用二進位制索引樹計算大小為3的反轉次數
透過程式計算給定陣列中大小為三的反轉次數來計算給定陣列中大小為三的反轉次數
對於計算大小為三的反轉的簡單方法，我們需要為所有可能的i、j和k值執行一個迴圈。時間複雜度為 O(n^3)，輔助空間為 O(1)。
條件是：
a[i] > a[j] > a[k] 且 i < j < k。
示例1
def getInvCount(arr):
n = len(arr)
invcount = 0
for i in range(0,n-1):
for j in range(i+1 , n):
if arr[i] > arr[j]:
for k in range(j+1 , n):
if arr[j] > arr[k]:
invcount += 1
return invcount
arr = [7 , 16, 2 , 1]
print ("Inversion Count after the operation: %d" %(getInvCount(arr)))
輸出
Inversion Count after the operation: 2
計算大小為3的反轉的更好方法
在此方法中，我們將考慮陣列的每個元素作為反轉的中間元素。這有助於降低複雜度。對於此方法，時間複雜度為 O(n^2)，輔助空間為 O(1)。
示例2
def getInvCount(arr, n):
invcount = 0
for i in range(1,n-1):
small = 0
for j in range(i+1 ,n):
if (arr[i] > arr[j]):
small+=1
great = 0;
for j in range(i-1,-1,-1):
if (arr[i] < arr[j]):
great+=1
invcount += great * small
return invcount
arr = [8, 4, 2, 1]
n = len(arr)
print("Inversion Count After The Method Run :",getInvCount(arr, n))
輸出
Inversion Count After The Method Run : 4
使用二進位制索引樹計算大小為3的反轉次數
在此方法中，我們也計算了較大和較小的元素。然後執行greater[]乘以smaller[]的操作，並將其新增到最終結果中。這裡時間複雜度為 O(n*log(n))，輔助空間表示為 O(n)。
示例3
def getSum( BITree, index):
sum = 0
while (index > 0):
sum += BITree[index]
index -= index & (-index)
return sum
def updateBIT(BITree, n, index, val):
while (index <= n):
BITree[index] += val
index += index & (-index)
def getInvCount(arr, n):
invcount = 0
maxElement = max(arr)
BIT = [0] * (maxElement + 1)
for i in range(n - 1, -1, -1):
invcount += getSum(BIT, arr[i] - 1)
updateBIT(BIT, maxElement, arr[i], 1)
return invcount
if __name__ =="__main__":
arr = [8, 4, 2, 1]
n = 4
print("Inversion Count After The Operation Done : ",
getInvCount(arr, n))
輸出
Inversion Count After The Operation Done : 6
結論
透過以上討論，我們學習瞭如何在給定陣列中計算大小為三的反轉次數。希望透過本文和使用特定語言提到的程式碼，您已經對這個主題有了廣泛的瞭解。
528 次瀏覽
