C++ 代码计算操作以使数组排序
假设我们有一个包含 n 个元素的数组 A(n 是奇数)。A 包含前 n 个自然数的排列。假设有一个函数f(i),它接受 0 到 n-2 范围内的单个参数 i,并执行以下操作:如果 A[i] > A[i+1],交换 A[i] 和 A[i+1 的值]。我们必须计算迭代次数以使数组 A 第一次排序。
所以,如果输入像 A = [4, 5, 7, 1, 3, 2, 6],那么输出就是 5,因为每次迭代后的数组状态就像:[4, 5, 1, 7 , 2, 3, 6], [4, 1, 5, 2, 7, 3, 6], [1, 4, 2, 5, 3, 7, 6], [1, 2, 4, 3, 5 , 6, 7], [1, 2, 3, 4, 5, 6, 7]。
脚步
为了解决这个问题,我们将遵循以下步骤 -
n := size of Af := 0
Ans := 0
for initialize Ans := 0, do:
f := 0
for initialize j := 0, when j < n - 1, update (increase j by 1), do:
if A[j] > A[j + 1], then:
f := 1
if not f is non-zero, then:
Come out from the loop
for initialize j := (Ans AND 1), when j < n - 1, update j := j + 2, do:
if A[j] > A[j + 1], then:
swap A[j] and A[j + 1]
(increase Ans by 1)
return Ans
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>using namespace std;
int solve(vector<int> A){
int n = A.size();
bool f = 0;
int Ans = 0;
for (Ans = 0;;){
f = 0;
for (int j = 0; j < n - 1; j++)
if (A[j] > A[j + 1])
f = 1;
if (!f)
break;
for (int j = (Ans & 1); j < n - 1; j += 2)
if (A[j] > A[j + 1])
swap(A[j], A[j + 1]);
Ans++;
}
return Ans;
}
int main(){
vector<int> A = { 4, 5, 7, 1, 3, 2, 6 };
cout << solve(A) << endl;
}
输入
{ 4, 5, 7, 1, 3, 2, 6 }输出结果
5
以上是 C++ 代码计算操作以使数组排序 的全部内容, 来源链接: utcz.com/z/297460.html