数据结构
网络连接
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 次查看
广告