Description

Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

Example

Given [1,2,4], return 1.

Solution

对每个数组中的数A[i]，它出现第index位给结果造成的增量为：（比A[i]小的还可以用的数）*（index位后面的数位的个数，即n-1-i）的阶乘
故用一个map存比数组中每个数小的数，注意，1. 存的时候要遍历sorted A，但是A的顺序后面还要用到，所以把A拷贝到另外一个数组上sort，2. map的value是比key小的可用的数，因此，在每使用了一个数之后，要更新map，把比已使用的数大的数的value-1

public class Solution {
    /*
     * @param A: An array of integers
     * @return: A long integer
     */
    public long permutationIndex(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }

        int n = A.length;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] arr = Arrays.copyOf(A, n);
        Arrays.sort(arr);
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }

        long[] factorial = new long[n];
        factorial[0] = 1;
        factorial[1] = 1;

        long ret = 1;
        for (int i = 0; i < 3; i++) {
            int v = map.get(A[i]);
            ret += v * factory(factorial, n - 1 - i);
            updateMap(map, A[i]);
        }

        return ret;
    }

    private long factory(long[] factorial, int n) {
        if (factorial[n] > 0) {
            return factorial[n];
        }

        factorial[n] = factory(factorial, n - 1) * n;
        return factorial[n];
    }

    private void updateMap(HashMap<Integer, Integer> map, int key) {
        for (int k : map.keySet()) {
            if (k > key) {
                map.put(k, map.get(k) - 1);
            }
        }
    }
}