775. 全局倒置与局部倒置

775. 全局倒置与局部倒置

题解：

1. 用归并排序求全局倒置（逆序对）
2. 可以用树状数组求逆序对

class Solution {
    int num2 = 0;
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;
        int num1 = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) num1++;
        }
        int[] temp = new int[n];
        mergeSort(nums, 0, n - 1, temp);
        return num1 == num2;
    }
    // 归并排序
    public void mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) return;
        int l = left, mid = (left + right) >> 1, r = mid + 1;
        mergeSort(nums, left, mid, temp);
        mergeSort(nums, mid + 1, right, temp);
        int k = l;
        while (l <= mid && nums[l] <= nums[r]) temp[k++] = nums[l++];
        // 逆序对
        while (r <= right && nums[l] > nums[r]) {
            num2 += r - l ;
            temp[k++] = nums[r++];
        }
        while (l <= mid) {
            temp[k++] = nums[l++];
        }
        while (r <= right) temp[k++] = nums[r++];
        for (int i = left; i <= right; i++) {
            nums[i] = temp[i];
        }
    }
}