資料結構
網路連線
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究C++ 中的全域性逆序和區域性逆序
假設我們有一些 [0, 1, ..., N - 1] 的排列 A，其中 N 為 A 的長度。現在，（全域性）逆序數就是 i < j 且 0 <= i < j < N 還有 A[i] > A[j] 的數量。並且區域性逆序數就是 i 且 0 <= i < N 還有 A[i] > A[i+1] 的數量。僅當全域性逆序數與區域性逆序數相等時，我們才將 true 返回。因此，如果輸入類似於 [1,0,2]，則返回 true，因為僅有一個區域性逆序和一個全域性逆序。
為了解決這個問題，我們將按照以下步驟進行操作
- maxVal := -1, n := A 的大小
- i 的範圍是 0 到 n – 3
- maxVal := A[i] 與 maxVal 中較大的那個
- 如果 maxVal > A[i + 2]；那麼返回 false
- 返回 true
讓我們看看以下實現來獲得更好的理解
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int maxVal = -1;
int n = A.size();
for(int i = 0; i < n - 2; i++){
maxVal = max(A[i], maxVal);
if(maxVal > A[i + 2])
return false;
}
return true;
}
};
main(){
vector<int> v = {1,0,2};
Solution ob;
cout << (ob.isIdealPermutation(v));
}輸入
[1,0,2]
輸出
1
更新於： 04-May-2020
296 次檢視
廣告