现有‘abcdefghijkl’12个字符，将其所有的排列按字典序进行排序，给出任意一组排列，说出这租排列在所有排列中是第几小的

- 日理万妓 2024-04-19 15:00 1阅读 0赞

题目：

据说这道题是百度校招的一道算法题，反正我觉得我在学校的时候很可能做不出来。在学校的时候真该好好学习啊，我也逃不过毕业之后再来后悔的命运。但是，我还是要说点正能量的话，

只要知道学，什么时候都不晚。至少现在我做这道题的时候没遇到太大的困难，说明毕业之后的学习还是有很大作用的。为了我喜欢的编程，为了我喜欢的算法，继续努力！

言归正传，我看到这道题的时候，原文有这道题的解法和思路，但是原谅我是学渣，看不懂那些数学公式

我的思路是，假如，给出的第一位是b（给出的这个字符串简称str），那么所有以a开头的字符串都会排在str前面。

以a开头的字符串的数量是多少呢？就是后面11位字符所有的排列组合，也就是11的阶乘。

如果第一位是c，那么所有以a或者b开头的所有字符串就会排在str的前面，也就是 2\*11！ （注意后面是11的阶乘，不是11），依次类推，可以知道第一位是任意字符时排在str前面的字符串的数量

接着看第二位，第二位的思路和第一位一样，同样可以知道第二位是任意字符时排在str前面的字符串的数量，以此类推，后面的字符都算完之后，把全部结果相加

但是，这个时候还有一个问题，在这道题中12个字符是固定的，所以假如第一位不是a，是b，那么a在后面的字符中一定会出现，同时b也不会再出现，所以在进行上面的计算时，不能直接以字典序来进行计算，在计算每一位时要根据尚未出现过得字符的顺序，来排列未出现的字符的顺序，具体看代码里的注释，不明白的地方debug一步一步看。

/**
         * 现有‘abcdefghijkl’12个字符，将其所有的排列按字典序进行排序，给出任意一组排列，说出这租排列在所有排列中是第几小的
         * System.out.println(getSortNum("abcdefghijlk")); //1
         * System.out.println(getSortNum("hgebkflacdji")); //302715242
         * System.out.println(getSortNum("gfkedhjblcia")); //260726926
         */
        public static int getSortNum(String value) {
            // 记录已经出现过得字符和未出现的字符顺序
            String sort = "abcdefghijkl";
            
            // 记录结果数
            int res = 1;
            for(int i=0;i<value.length();i++) {
                // 依次取各位的字符
                char c = value.charAt(i);
                // 查看该字符在所有字符中的当前顺序
                int head = sort.lastIndexOf(c);
                // 计算排在前面的字符串数量
                res += ((head-i)*factorial(11-i));
                
                // 修改字符顺序，将当前出现的字符，交换到字符最前面
                // 因为我们不关心已经出现过得字符的顺序，我们只要知道出现过哪些字符以及未出现的字符的字典序
                // 所以直接把出现过得字符扔到最前面就可以了
                sort = change(sort, head);
            }
            return res;
        }
        
        /**
         * 求阶乘
         * @param i
         * @return
         */
        public static int factorial(int i) {
            if(i==0) return 0;
            int result = 1;
            for(;i>1;i--) {
                result *= i;
            }
            return result;
        }
    
            /**
         * 将字符串第a位换到最前面
         * @param str
         * @param a
         * @param b
         * @return
         */
        public static String change(String str,int a) {
            char[] chars = str.toCharArray();
            char temp = chars[a];
            for(int i=a;i>0;i--) {
                chars[i] = chars[i-1];
            }
            chars[0] = temp;
            return String.valueOf(chars);
        }

来源：[https://www.cnblogs.com/wsss/p/5473487.html][https_www.cnblogs.com_wsss_p_5473487.html]

[https_www.cnblogs.com_wsss_p_5473487.html]: https://www.cnblogs.com/wsss/p/5473487.html