775. 全局倒置与局部倒置

 

【归并排序】显然全局倒置就是求整体的逆序对，用归并排序的思想可以在O(nlogn)的复杂度下求出逆序对的个数。

class Solution {// 9:56 15int[] nums, tmp;int n;int global(int l, int r) {if (l == r) return 0;int m = (l + r) >> 1;int ret = 0;ret += global(l, m); ret += global(m + 1, r);int i = l, j = m + 1, k = 0;while (i <= m && j <= r) {if (nums[i] > nums[j]) {tmp[k++] = nums[i++];ret += r - j + 1;} else {tmp[k++] = nums[j++];}}while (i <= m) tmp[k++] = nums[i++];while (j <= r) tmp[k++] = nums[j++];for (i = l, k = 0; i <= r;) nums[i++] = tmp[k++];return ret;}int local() {int ret = 0;for (int i = 0; i < n - 1; i++) {if (nums[i] > nums[i + 1]) ret++;}return ret;}public boolean isIdealPermutation(int[] nums) {this.nums = nums;n = nums.length;tmp = new int[n];if (local() == global(0, n - 1)) return true;return false;}
}

【数学】我们发现局部倒置一定是全局倒置，如果数量相同就是所有的全局倒置都是局部的，也就是都是相邻的，那么只需要检查一下有没有不相邻的倒置即可。

 

class Solution {// 维护后缀最小值// 10:56 3public boolean isIdealPermutation(int[] nums) {int n = nums.length, min = nums[n - 1];for (int i = n - 3; i >= 0; i--) {if (nums[i] > min) return false;min = Math.min(nums[i + 1], min);}return true;}
}