197. 排列序号

题目

给出一个不含重复数字的排列,求这些数字的所有排列按字典序排序后该排列的编号。其中,编号从1开始。http://www.lintcode.com/zh-cn/problem/permutation-index/

分析

这个题目和例子有点太简略了,稍微解释一下是什么意思。比如给定了一个数字排列{2, 1, 4},这个排列中的所有元素,能够形成的所有排列按照字典顺序如下:

{1, 2, 4}
{1, 4, 2}
{2, 1, 4}
{2, 4, 1}
{4, 1, 2}
{4, 2, 1}

而{2, 1, 4}这个排列是第3个,所以结果应该输出3 。

很显然这是一道排列组合的题目,如果真的去计算出全部的排列情况,再去对比其顺序肯定是效率太低了。以{2, 1, 4}组合为例,我们可以这样计算它在最终字典排序里的顺序:

  1. 第一位如果是1,那么这些组合肯定排在2开头的排列前面,一共有2!个
  2. 第一位如果是4,肯定排在2后面,不用考虑了
  3. 第一位如果是2,那么就看第二位起往后的元素,这时只要递归前两个步骤,就能算出来排在当前排列前面的可能数量
  4. 重复这个过程,得解

代码


public class Solution {
    
    long An(long n){
        long total = 1;
        for(long i=1; i<=n; i++){
            total *= i;
        }
        return total;
    }

    long lessThan(int[] A, int start){
        long count = 0;

        for(int i=start+1; i < A.length; i++){
            if(A[i] < A[start]) count++;
        }

        return count;
    }



    /*
     * @param A: An array of integers
     * @return: A long integer
     */
    public long permutationIndex(int[] A) {
        long total = 0;

        for(int i=0; i < A.length; i++){
            total += lessThan(A, i) * An(A.length - i - 1);
        }
        return total + 1;

    }

}
Show Comments

Get the latest posts delivered right to your inbox.