网站搜索

用于计算给定数组中大小为 3 的反转的 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]的数字。

计算数组中大小为 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

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;

这里我们提到了计算给定数组中大小为 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。

实施例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

结论

从上面的讨论中,我们学习了如何计算给定数组中大小为 3 的反转。希望通过本文和提到的使用特定语言的代码,您对这个主题有一个广泛的了解。

相关文章: