資料結構
網路
關係型資料庫管理系統
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究計算陣列排序所需操作的 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 A f := 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
更新於：2022 年 3 月 15 日
261 次瀏覽
廣告