数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
