給定一個數組，寫一個PHP程式來計算大小為三的逆序對數量-php教程-PHP中文網

給定一個數組，寫一個PHP程式來計算大小為三的逆序對數量

PHPz

發布： 2023-09-02 19:50:01

轉載

612 人瀏覽過

給定一個數組，寫一個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]大的數。

計算數組中大小為 3 的反轉的演算法：-

在這個演算法中；我們學習如何在特定的程式環境中計算給定數組中大小為 3 的反轉。

第 1 步 - 開始
第 2 步 - 宣告陣列與反轉計數（如 arr[] --> 陣列與 invCount --> 反轉計數）
#第 3 步 - 內循環 y=x 1 到 N
步驟 4 - 如果 x 處的元素大於 y 索引處的元素
第 5 步 - 然後增加 invCount
#第 6 步 - 列印該對
第 7 步 - 終止

計算數組中大小為 3 的反轉的語法：-

若符合下列條件，則稱一對 (A[i], A[j]) 為反轉狀態：A[i] > A[j] 且 i < j< 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));
?>

登入後複製

這裡我們提到了計算給定數組中大小為 3 的反轉的可能語法。對於這個方法；時間複雜度為 O(N^2)，其中 N 是陣列的總大小；空間複雜度：O(1)，因為沒有使用額外的空間。

遵循的方法：-

方法 1 - 透過程式計算給定數組中大小為 3 的反轉，以計算大小為 3 的反轉
方法 2 - 計算大小 3 的反轉的更好方法
方法 3 - 使用二元索引樹計算大小為 3 的反轉

#透過程式對給定數組中大小為 3 的反轉進行計數，以計算大小為 3 的反轉

對於計算大小為 3 的反轉的簡單方法，我們需要對 i、j 和 k 的所有可能值執行一個迴圈。時間複雜度為O(n^3)，O(1)反映了輔助空間。

條件是：

a[i] > a[j] > a[k] 且 i < j < k。 < 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);
?>

登入後複製