Permutation Index 197

Question

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

这道题因为没有重复元素，所以比较简单。主要思想为找出当前位元素的index，然后将各位加起来即可。

然后顺序遍历A中的元素，求当前元素的index：小于当前元素的可用元素的数量 * 之后元素数量的阶乘。然后要更新map，因为当前元素在这次已经使用，所以在map里的比当前元素大的元素的value要－1。

代码如下：

public class Solution {
    /**
     * @param A an integer array
     * @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;
        //为了防止操作改变A的顺序，要复制一份来排序
        int[] array = Arrays.copyOf(A, n);
        Arrays.sort(array);
        //将有多少个元素小于当前元素的信息存在map中
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < n; i++){
            map.put(array[i], i);
        }

        //index start from 1
        long sum = 1;
        for(int i = 0; i < n; i++){
            sum += map.get(A[i]) * factor(n - 1 - i);
            updateMap(map, A[i]);
        }

        return sum;
    }

    private long factor(int n){
        long now = 1;
        for(int i = 1; i <= n; i++){
            now *= (long) i;
        }
        return now;
    }

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