两分钟看完一道数学思想的算法题

谁践踏了优雅 2021-11-02 03:26 262阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | P.yh

来源 | 五分钟学算法

### 题目描述 ###

给你数字 0 ，1 ，2 ，那么所有排列从小到大就会是 012，021，102，120，201，210，那么如果给你 0，1，2，3，4，5，6，7，8，9 让你去排，从小到大排在第一百万的数是多少？

题目地址：https://projecteuler.net/problem=24

### 题目解析 ###

写普通算法程序题写多了，见到 **排列** 首当其冲想到用深度优先搜索，最后发现如果把所有的排列可能都给列出来，然后排序，这样搞下来程序运行的时间复杂度是 **O(n!)**，比指数的时间复杂度还要高！

如果从数学思路上去思考的话，那问题就简单了！

**通过一个数一个数的去选**。

首先第一个位置（最高位）有十种可能性，我们可以利用 10! / 10 来计算出每一个数字打头有多少种排列，然后用 **一百万 / (10! / 10)** 来决定我们要选排在第几的数，选中一个数后，剩下的数就只有 9 个，将 10 换成 9，重复上面的操作，当然，一百万这个值也得根据我们找的数来做更新，比如你第一个数选择了 2，那么 0 和 1 打头的 **2 \* 10! / 10** 种组合都可以减掉，剩下的我们需要继续在后面的 9 个数的排列中找。

### 代码实现 ###

//@author:P.yhpublic static void main(String[] args) {    System.out.println(lexicographicPermu(10, 1000000L));}private static String lexicographicPermu(int numberOfDigit, long target) {    int copyOfNumerOfDigit = numberOfDigit;    long copyOfTarget = target;    // list 里面存放的是所有的可以选择的情况，并从大到小排列    // 这里是 0，1，2，3，4，5，6，7，8，9    List<Integer> candidate = new ArrayList<>();    for (int i = 0; i < copyOfNumerOfDigit; ++i) {        candidate.add(i);    }    String result = "";    // 只要没有选完，就继续选择    while (copyOfNumerOfDigit != 0) {        long totalPermutation = 1;        int n = copyOfNumerOfDigit;        // 计算 n!        // 例如，选择第一个数，那 totalPermutation 就是 10!        while (n != 1) {            totalPermutation *= n;            n--;        }        // 计算选择当前情况下的第几个数        // 这里 copyOfTarget - 1 是为了防止整除的情况        // 举 0，1，2 这个例子，当我们要选择排在第 2 的那个数，也就是 021        // 选第一个数的时候， totalPermutation = 3 * 2 * 1 = 6, copyOfNumberOfDigit = 3        // 2 / (6 / 3) = 1，显然不符合要求，(2 - 1) / (6 / 3) = 0 才是选中了 0        int selection = (int)((copyOfTarget - 1) / (totalPermutation / copyOfNumerOfDigit));        result += candidate.remove(selection);        // 更新下一次要选择第几个数        copyOfTarget -= (totalPermutation / copyOfNumerOfDigit) * selection;        // 选了一个数，可选项相应减少一        copyOfNumerOfDigit--;        copyOfTarget = copyOfTarget <= 0 ? 0 : copyOfTarget;    }    return result;}
    public static void main(String[] args) {
        
        System.out.println(lexicographicPermu(10, 1000000L));
    }
    
    private static String lexicographicPermu(int numberOfDigit, long target) {
        
        int copyOfNumerOfDigit = numberOfDigit;
        long copyOfTarget = target;
    
        // list 里面存放的是所有的可以选择的情况，并从大到小排列
        // 这里是 0，1，2，3，4，5，6，7，8，9
        List<Integer> candidate = new ArrayList<>();
        for (int i = 0; i < copyOfNumerOfDigit; ++i) {
        
            candidate.add(i);
        }
    
        String result = "";
    
        // 只要没有选完，就继续选择
        while (copyOfNumerOfDigit != 0) {
        
            long totalPermutation = 1;
            int n = copyOfNumerOfDigit;
    
            // 计算 n!
            // 例如，选择第一个数，那 totalPermutation 就是 10!
            while (n != 1) {
        
                totalPermutation *= n;
                n--;
            }
    
            // 计算选择当前情况下的第几个数
            // 这里 copyOfTarget - 1 是为了防止整除的情况
            // 举 0，1，2 这个例子，当我们要选择排在第 2 的那个数，也就是 021
            // 选第一个数的时候， totalPermutation = 3 * 2 * 1 = 6, copyOfNumberOfDigit = 3
            // 2 / (6 / 3) = 1，显然不符合要求，(2 - 1) / (6 / 3) = 0 才是选中了 0
            int selection = (int)((copyOfTarget - 1) / (totalPermutation / copyOfNumerOfDigit));
            result += candidate.remove(selection);
    
            // 更新下一次要选择第几个数
            copyOfTarget -= (totalPermutation / copyOfNumerOfDigit) * selection;
    
            // 选了一个数，可选项相应减少一
            copyOfNumerOfDigit--;
            copyOfTarget = copyOfTarget <= 0 ? 0 : copyOfTarget;
        }
    
        return result;
    }

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20211102/a14ac49279414d39abab1d851b88a61f.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20211102/6f4bbd93036d4bd09ddb2260176ec4ae.png