ウェブサイト検索

指定された配列内のサイズ 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

反転カウントは、その特定の配列が昇順でのソートからどの程度離れているかを示します。この状況を説明するための解決策を伴う 2 つの特定のプロセスを次に示します-

  • より小さい要素を見つけるには: 配列からより小さい要素を見つけるには、インデックスを 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[] と small[] の乗算演算を実行し、それを最終結果に加算します。ここで、時間計算量は 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 の反転を数える方法を学びました。この記事と、特定の言語を使用した言及されたコードを読んで、このトピックについて広い視野を持っていただければ幸いです。

関連記事: