775. Global and Local Inversions

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].

The number of global inversions is the number of the different pairs (i, j) where:

• 0 <= i < j < n
• nums[i] > nums[j]

The number of local inversions is the number of indices i where:

• 0 <= i < n - 1
• nums[i] > nums[i + 1]

Return true if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

Example 2:

Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.

Constraints:

• n == nums.length
• $1 <= n <= 10^5$
• 0 <= nums[i] < n
• All the integers of nums are unique.
• nums is a permutation of all the numbers in the range [0, n - 1].

Code

• 是 global 但是不是 local 的情况: 差两个位置, 是 nums[i] > nums[j]的情况

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        int mn = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 2; --i) {
            mn = Math.min(mn, nums[i]);
            if (nums[i - 2] > mn) return false;
        }
        return true;
    }
}

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i] - i) > 1) return false;
        }

        return true;
    }
}

class Solution {
    int[] temp;

    public boolean isIdealPermutation(int[] nums) {
        int size = nums.length;
        temp = new int[size];
        int local = 0;
        for (int i = 1; i < size; i++) {
            if (nums[i] < nums[i - 1]) local++;
        }

        int global = mergeSort(nums, 0, size - 1);
        return global == local;
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;

        int middle = left + (right - left) / 2;
        int inv = mergeSort(nums, left, middle) + mergeSort(nums, middle + 1, right);

        // 左边和右边数组的开始
        int i = left;
        int j = middle + 1;
        int k = 0;

        while (i <= middle && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                inv += middle - i + 1;
            }
        }

        while (i <= middle) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];

        for (int m = 0; m < k; m++) {
            nums[left + m] = temp[m];
        }

        return inv;
    }
}