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

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 – 通过计数大小为3的逆序的程序来计算给定数组中大小为三的逆序

• 方法2 – 更好的方法来计算大小为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

结论

通过以上讨论，我们已经学会了如何在给定数组中计算大小为三的逆序对。希望通过本文章和使用特定语言的代码，您已经对这个主题有了一个广泛的了解。