前言

之前刷过一些leetcode的题目，这学期修了组合数学这门课，让我感受颇多。课程上更关注的是数学上的解法，并没有讲到具体的用某种语言实现，并没有深入地讲为什么这样做就是对的。结合我的经验，想分享一下我的理解。

leetcode 31.下一个全排列

31.下一个全排列

2个关键点:

下一个全排列比当前的大(字典序)
增量要是最小的

一些例子:

1243 -> 1324,要使1243更大，从右往左看，43已经是最大的了,所以下一个肯定是13开头，故交换2,3得到1342,后2位42肯定无法保证增量最小，故翻转42，得到1324,即为所求
4321 -> 1234,从右往左看，全部递增，故这是最后一个序列了，翻转整个序列，得到1234,符合题目的要求


class Solution {

    public void nextPermutation(int[] nums) {

        if(nums == null || nums.length ==  1) return;

        //从右向左，找到破坏递增规律的第一个数

        int n = nums.length;

        int index = -1;

        for(int i = n-2; i >= 0; i--){

            if(nums[i] < nums[i+1]){

                index = i;

                break;

            }

        }

        //找到比nums[index]大的第一个数

        //交换nums[index]与这个nums[i]

        if(index != -1){

            for(int i = n-1; i>= 0; i--){

            if(nums[i] > nums[index]){

                int tmp = nums[i];

                nums[i] = nums[index];

                nums[index] = tmp;

                break;

            }

        }

        }

        //翻转数组，范围为[index+1,n-1]，这样便使增量最小

        //如果是最后一个排列，如[3,2,1],index为-1，翻转整个序列

        reverseArray(nums, index+1, n-1);

    }

    public void reverseArray(int[] nums,int start,int end){

        for(int i = start, j = end;i <= j; i++,j--){

            //交换nums[i]与nums[j]

            int tmp = nums[i];

            nums[i] = nums[j];

            nums[j] = tmp;

        }

    }

}

leetcode 60.第k个全排列

n=3时，共有3!个排列

123
132
213
231
312
321

关键:

每2个看成一组，每一组内第一位都是相同的,如123,132
即每n-1个看成一组，总共有n组(n!=n*(n-1))
若第0位已确定，剩下就是n-1个数的排列，可分成n-1组，每个组内(n-2)!个

以n=3,k=4为例:

为了跟程序里的小标对应,从0开始，k=k-1=3
3/2!=1余1,说明第0位是[1,2,3]中下标为1的数,即2
余数为1，剩下2个数,1/1!=1余0,[1,3]中下标为1的数即3
只剩下1,故结果是231

这其实可以归纳出一个数学公式，康托展开与逆展开


class Solution {

    public String getPermutation(int n, int k) {

        //需要用到一点数学知识，康托展开

        StringBuilder sb = new StringBuilder();

        List<Integer> info = new ArrayList<Integer>();

        for(int i=1;i<=n;i++){

            info.add(i);

        }

        int factor=1;

        k=k-1;

        //计算出(k-1)!

        for(int i = 2;i<=n-1;i++){

            factor *= i;

        }

        for(int i=n-1;i>=1;i--){

            int p = k/factor;//商

            k = k%factor;//余数

            sb.append(info.get(p));

            //移除

            info.remove(p);

            //更新

            factor /= i;

        }

        sb.append(info.get(0));//最后info中只剩下一个

        return sb.toString();

    }

}