資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學PHP程式：計算給定陣列中大小為三的逆序對
逆序對計數是一種步數計數方法，我們可以用它來計算特定陣列排序所需的步驟數。它也可以計算陣列的操作時間跨度。但是，如果我們想以相反的方式排序陣列，則計數將是該陣列中存在的最大數字。
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;
}
PHP 實現
<?php
$a=array("a "=>"Volvo","b"=>"BMW","c"=>"Toyota");
print_r(array_reverse($a));
?>
這裡我們提到了在給定陣列中計算大小為三的逆序對的可能語法。對於此方法；時間複雜度為 O(N^2)，其中 N 是陣列的總大小；空間複雜度為 O(1)，因為沒有使用額外的空間。
遵循的方法：
方法 1 - 透過程式計算給定陣列中大小為 3 的逆序對
方法 2 - 計算大小為 3 的逆序對的更好方法
方法 3 - 使用二進位制索引樹計算大小為 3 的逆序對
透過程式計算給定陣列中大小為 3 的逆序對
對於計算大小為三的逆序對的簡單方法，我們需要為所有可能的 i、j 和 k 值執行迴圈。時間複雜度為 O(n^3)，O(1) 反映了輔助空間。
條件是
a[i] > a[j] > a[k] 且 i < j < k。
示例 1
<?php
function getInvCount($arr, $n){
$invcount = 0;
for ($i = 1; $i < $n - 1; $i++){
$small = 0;
for($j = $i + 1; $j < $n; $j++)
if ($arr[$i] > $arr[$j])
$small++;
$great = 0;
for($j = $i - 1; $j >= 0; $j--)
if ($arr[$i] < $arr[$j])
$great++;
$invcount += $great * $small;
}
return $invcount;
}
$arr = array(16, 7, 22, 10);
$n = sizeof($arr);
echo "Inversion Count : "
, getInvCount($arr, $n);
?>
輸出
Inversion Count : 0
計算大小為 3 的逆序對的更好方法
在此方法中，我們將陣列的每個元素都視為逆序對的中間元素。這有助於降低複雜度。對於這種方法，時間複雜度為 O(n^2)，輔助空間為 O(1)。
示例 2
<?php
function getInvCount($arr, $n){
$invcount = 0;
for ($i = 1; $i < $n - 1; $i++){
$small = 0;
for ($j = $i + 1; $j < $n; $j++)
if ($arr[$i] > $arr[$j])
$small++;
$great = 0;
for ($j = $i - 1; $j >= 0; $j--)
if ($arr[$i] < $arr[$j])
$great++;
$invcount += $great * $small;
}
return $invcount;
}
$arr = array (81, 14, 22, 7);
$n = sizeof($arr);
echo "Inversion Count For The Input Is : " ,
getInvCount($arr, $n);
?>
輸出
Inversion Count For The Input Is : 2
使用二進位制索引樹計算大小為 3 的逆序對
在此方法中，我們也計算較大元素和較小元素。然後執行 greater[] 與 smaller[] 的乘法運算，並將其新增到最終結果中。這裡的時間複雜度為 O(n*log(n))，輔助空間表示為 O(n)。
示例 3
<?php
function getInvCount($arr, $n) {
$invcount = 0;
for ($i = 1; $i < $n - 1; $i++){
$small = 0;
for ($j = $i + 1; $j < $n; $j++)
if ($arr[$i] > $arr[$j])
$small++;
$great = 0;
for ($j = $i - 1; $j >= 0; $j--)
if ($arr[$i] < $arr[$j])
$great++;
$invcount += $great * $small;
}
return $invcount;
}
$arr = array (811, 411, 16, 7);
$n = sizeof($arr);
echo "Inversion Count After The Process : " ,
getInvCount($arr, $n);
?>
輸出
Inversion Count After The Process : 4
結論
在本文中，我們瞭解瞭如何在給定陣列中計算大小為三的逆序對。希望透過本文和使用特定語言提到的程式碼，您對這個主題有了廣泛的瞭解。
瀏覽量：159
