建设的基本流程网站,企业网站建站公司郑州,wordpress防恶意注册,建设银行新乡分行城南支行网站文章目录1. 题目2. 解题2.1 归并排序求逆序度2.2 二分查找2.3 一次遍历1. 题目
数组 A 是 [0, 1, ..., N - 1] 的一种排列#xff0c;N 是数组 A 的长度。
全局倒置指的是 i,j 满足 0 i j N 并且 A[i] A[j] #xff0c;局部倒置指的是 i 满足 0 i…
文章目录1. 题目2. 解题2.1 归并排序求逆序度2.2 二分查找2.3 一次遍历1. 题目
数组 A 是 [0, 1, ..., N - 1] 的一种排列N 是数组 A 的长度。
全局倒置指的是 i,j 满足 0 i j N 并且 A[i] A[j] 局部倒置指的是 i 满足 0 i N 并且 A[i] A[i1] 。
当数组 A 中全局倒置的数量等于局部倒置的数量时返回 true 。
示例 1:
输入: A [1,0,2]
输出: true
解释: 有 1 个全局倒置和 1 个局部倒置。示例 2:
输入: A [1,2,0]
输出: false
解释: 有 2 个全局倒置和 1 个局部倒置。注意:
A 是 [0, 1, ..., A.length - 1] 的一种排列
A 的长度在 [1, 5000]之间来源力扣LeetCode 链接https://leetcode-cn.com/problems/global-and-local-inversions 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 归并排序求逆序度
参考剑指Offer - 面试题51. 数组中的逆序对归并排序求逆序对
class Solution {int local 0, global 0;vectorint tmp;
public:bool isIdealPermutation(vectorint A) {if(A.size() 1) return true;for(int i 0; i A.size()-1; i)if(A[i] A[i1])local;tmp.resize(A.size());mergesort(A, 0, A.size()-1);return local global;//逆序度 局部逆序度}void mergesort(vectorint A, int l, int r){if(l r) return;int mid (lr)/2;mergesort(A, l, mid);mergesort(A, mid1, r);int i l, j mid1, k 0;while(i mid j r){if(A[i] A[j])tmp[k] A[i];else//后序写入时检查前面没有出队的比我大我在后面{tmp[k] A[j];global mid-i1;}}while(i mid)tmp[k] A[i];while(j r)tmp[k] A[j];k 0; i l;while(i r)A[i] tmp[k];}
};时间复杂度 O(nlogn)O(n\log n)O(nlogn) 192 ms 33.8 MB
2.2 二分查找
全局倒置数量肯定 局部倒置数量检查每个数字 A[i]A[i]A[i]它的前面 [0,i−2][0, i-2][0,i−2] 相邻的不需要检查存在比它大的数肯定不满足题意
class Solution {
public:bool isIdealPermutation(vectorint A) {setint s;s.insert(A[0]);for(int i 2; i A.size(); i){if(s.lower_bound(A[i]1) ! s.end()){ //前面存在比 A[i] 大的数return false;}s.insert(A[i-1]);}return true;}
};时间复杂度 O(nlogn)O(n\log n)O(nlogn) 396 ms 52.1 MB
2.3 一次遍历
优化在第二种方法的基础上记录前面的最大值即可
class Solution {
public:bool isIdealPermutation(vectorint A) {int MAX A[0];for(int i 2; i A.size(); i){if(MAX A[i])return false;MAX max(MAX, A[i-1]);}return true;}
};时间复杂度 O(n)O(n)O(n) 148 ms 32.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
