给定一个数组，编写一个PHP程序来计算大小为三的逆序对数量-php教程-PHP中文网

给定一个数组，编写一个PHP程序来计算大小为三的逆序对数量

PHPz

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

转载

608 人浏览过

给定一个数组，编写一个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);
?>

登录后复制