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

点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午12:15,一起学算法作者|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题目解析写普通算法...

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

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

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

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;
}



本文相关阅读推荐:


毕业十年后,我忍不住出了一份程序员的高考试卷

一道腾讯面试题:厉害了我的杯

十大经典排序算法动画与解析,看我就够了

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

面试官,我会写二分查找法!对,没有 bug 的那种!

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

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

640?wx_fmt=png

源文地址:https://www.guoxiongfei.cn/csdn/7547.html