775. Global and Local Inversions

开源项目
1

We have some permutation A of [0, 1, ..., N - 1] , where N is the length of A .

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j] .

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1] .

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

Example 1:

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

Example 2:

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

Note:

  • A will be a permutation of [0, 1, ..., A.length - 1] .
  • A will have length in range [1, 5000] .
  • The time limit for this problem has been reduced.

思路

值的范围是从0~A.length-1，设想一种情况：

风平浪静，一切都好，既没有global，也没能local

0 1 2 3 4
0 1 2 3 4

如果4放到了位置2，那么无论怎么摆放其他数字，4一定比后面某二个数字大：

0 1 2 3 4
* * 4 * *

试想下面这种极端情况：

0 1 2 3 4 5 6 7
* * 4 5 6 7 * *

同理，如果把2放到位置3，无论怎么摆放数字，2都比前面的某个数字小：

0 1 2 3 4
* * * 2 *

依据这个规律可以进行计算：如果发现|A[i] - i| > 1，说明A[i]的前/后，一定存在多个k，k的值一定大于/小于A[i]，那么一定会让global多于local。

java

image
image917×296 17.1 KB 

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

我理解是倒序？

public class FanXu {
    static int[] Backorder (int[]A)
    {
        int temp;
        for(int i = 1;i < A.length; i++)
        {
            for(int y = 0 ; y < A.length-i ;y++)
            {
                if(A[y] < A[y+1])
                {
                    temp = A[y];
                    A[y] = A[y+1];
                    A[y+1] = temp;
                }
            }
        }
        return A;

    }

    public static void main(String[] args) {
        int[] num = {1,2,3,4,5,6,7,8,9};
        for (int C:Backorder(num))
        {
            System.out.println(C);
        }

    }
}
3

应该不是这个意思