数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：计算给定数组中大小为三的反转次数
反转计数是一种步数计数方法，我们可以用它来计算特定数组的排序步骤数。它也可以计算数组的操作时间跨度。但是，如果我们想以相反的方式排序数组，则计数将是该数组中存在的最大数字。
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 - 通过程序计算给定数组中大小为 3 的反转次数来计算给定数组中大小为三的反转次数
方法 2 - 更好的方法来计算大小为 3 的反转次数
方法 3 - 使用二进制索引树计算大小为 3 的反转次数
通过程序计算给定数组中大小为 3 的反转次数来计算给定数组中大小为三的反转次数
对于计算大小为三的反转次数的简单方法，我们需要为 i、j 和 k 的所有可能值运行循环。时间复杂度为 O(n^3)，O(1) 反映辅助空间。
条件是：
a[i] > a[j] > a[k] 且 i < j < k。
示例 1
#include<bits/stdc++.h>
using namespace std;
int getInvCount(int arr[],int n){
int invcount = 0;
for (int a=0; a<n-2; a++){
for (int j=a+1; j<n-1; j++)
{
if (arr[a]>arr[j])
{
for (int k=j+1; k<n; k++)
{
if (arr[j]>arr[k])
invcount++;
}
}
}
}
return invcount;
}
int main(){
int arr[] = {7, 10, 1, 97};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Inversion Count : " << getInvCount(arr, n);
return 0;
}
输出
Inversion count after method: 0
更好的方法来计算大小为 3 的反转次数
在这种方法中，我们将数组的每个元素都视为反转的中间元素。这有助于降低复杂度。对于这种方法，时间复杂度为 O(n^2)，辅助空间为 O(1)。
示例 2
#include<bits/stdc++.h>
using namespace std;
int getInvCount(int arr[], int n){
int invcount = 0;
for (int i=1; i<n-1; i++){
int small = 0;
for (int j=i+1; j<n; j++)
if (arr[i] > arr[j])
small++;
int great = 0;
for (int j=i-1; j>=0; j--)
if (arr[i] < arr[j])
great++;
invcount += great*small;
}
return invcount;
}
int main(){
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Inversion Count After The Method: " << getInvCount(arr, n);
return 0;
}
输出
Inversion Count After The Method: 4
使用二进制索引树计算大小为 3 的反转次数
在这种方法中，我们也计算较大和较小的元素。然后执行 greater[] 与 smaller[] 的乘法运算，并将其添加到最终结果中。这里的时间复杂度为 O(n*log(n))，辅助空间表示为 O(n)。
示例 3
import java.io.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.lang.*;
import java.util.Collections;
public class rudrabytp {
static int N = 100005;
static int BIT[][] = new int[4][N];
static void updateBIT(int t, int i, int val, int n) {
while (i <= n) {
BIT[t][i] = BIT[t][i] + val;
i = i + (i & (-i));
}
}
static int getSum(int t, int i) {
int res = 0;
while (i > 0) {
res = res + BIT[t][i];
i = i - (i & (-i));
}
return res;
}
static void convert(int arr[], int n){
int temp[]=new int[n];
for (int i = 0; i < n; i++)
temp[i] = arr[i];
Arrays.sort(temp);
for (int i = 0; i < n; i++) {
arr[i] = Arrays.binarySearch(temp,arr[i]) + 1;
}
}
public static int getInvCount(int arr[], int n) {
convert(arr, n);
for (int i = n - 1; i >= 0; i--) {
updateBIT(1, arr[i], 1, n);
for (int l = 1; l < 3; l++) {
updateBIT(l + 1, arr[i], getSum(l, arr[i] - 1), n);
}
}
return getSum(3, n);
}
public static void main (String[] args) {
int arr[] = {8, 4, 2, 1};
int n = arr.length;
System.out.print("Inversion Count After The Operation : "+getInvCount(arr,n));
}
}
输出
Inversion Count After The Operation : 4
结论
在本文中，我们今天学习了如何在给定数组中计算大小为三的反转次数。希望通过本文和使用特定语言提到的代码，您已经对这个主题有了广泛的了解。
167 次浏览
