javascript算法题：求任意一个1-9位不重复的N位数在该组合中的大小排列序号

具体题目是这样的：

　　从1--9中选取N个数字，组成不重复的N位数，从小到大进行编号，当输入其中任何一个数M时，能找出该数字对应

的编号。如 N=3，M=213.     输出：[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2

　　首先看到题目想到的是生成一个从少到大的全排列的数组，然后再遍历数组得到对应的序号(数组下标加1)，又或者想到一个个从小到大的生成push进数组，然后判断该数是不是当前题目给的数，如果是的话要求的序号就是当前数组的长度，比前面好的一点的是不用浪费时间去计算生成后面的项。生成本身复杂度不高，如果扩展到16进制甚至36进制且给一个很大的数的话就不好了，还有需要浪费一部分空间去保存用不上的数据。或许我们可以尝试其它不用生成的方法。

　　我们先理想化下题目，如果给了一个数N，那么，M就由1-N N位数组成（比如N=4,那M就由1234几个数字组合，而不是其它1349等其它组合）。之所以这么做是因为我们要简化条件好分析出共性得到解题的方法，而且要从随机的情况转化成理想的情况也不难，本文就不啰嗦了。先分析下题目给的例子，[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)] 213在第三位，首数字是2，也就是说首数字是1的都在他前面(123,132)，再来看第二个数字和后面的数的组合13，首字母1已经是最小的了，他前面不可能有任何数，而第三个数字3就不用看了，因为如果前面的位数都确定了，最后一位就只有一种可能了，得出来的结果就是213的前面有2(首位)+0(二位)+0(尾位)=2个数，也就是说当前数在第3位，对比一下答案确实是这样的，其它数的分析也一样。由此可以得出我们要一个函数(也就是下面代码的setAll())可以算出某一位比当前数小的可能性总数，然后累加起来+1就是想要的结果，请看代码实现：

//函数功能:得到每一位，如果是其它数的话比当前小的可能性总数
//a  当前数序号（从小到大）
//n  当前数总数
function getAll(a,n){
 var sum=1; //总数
 for(var i=n;i>1;i--)sum=sum*i; //算出n个有序的位置放n个不同的数字的可能性总数
 return sum*(a-1)/n; //算出比首位为a的比当前数小的数的可能性总数
}

//m 要计算的数序列
//a 存放当前位的数在和它后位的数而组成的数它的大小序号
//  比如 213 的 a数组为 [2,1,1]; a[0]为2是因为 213 首位2在213三个数字中排第2小;而a[1]为1是因为13的首位1在13中排第一小
function find(m){
 m=(m+"").split(""); //把当前数拆分放在数组里面好方便对每一位进行计算
 var a=new Array(m.length+1).join(1).split(""); //快速生成长度为m的长度的值都为1的数组，a数组的功能说明看上面函数头的注释
 for(var i=0;i<m.length-1;i++){
 for(var j=i+1;j<m.length;j++){
  if(+m[i]>+m[j])a[i]++;
 }
 } //生成a数组
 console.log("a数组：",a);
 for(i=1,sum=1;i<m.length;i++){
 sum+=getAll(+a[i-1],m.length-i+1); //循环调用getAll计算每一位与其后面的数成的组合比当前组合小的可能性总数
 }
 return m+" 排在全排列的第"+sum+"位";
}
console.log(find(213)); //输出3
console.log(find(123)); //输出1
console.log(find(231)); //输出4
console.log(find(312)); //输出5
console.log(find(4321)); //输出24
console.log(find(21)); //输出2
console.log(find(1)); //输出1
赞 (0)

相关推荐

  • 很好用的js日历算法详细代码

    复制代码 代码如下: <script type="text/javascript">         var lunarInfo = new Array( 0x04bd8, 0x04ae0, 0x0a570, 0x054d5, 0x0d260, 0x0d950, 0x16554, 0x056a0, 0x09ad0, 0x055d2, 0x04ae0, 0x0a5b6, 0x0a4d0, 0x0d250, 0x1d255, 0x0b540, 0x0d6a0, 0x0ada2,

  • javascript算法题 求任意一个1-9位不重复的N位数在该组合中的大小排列序号

    具体题目是这样的: 从1--9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号.如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2 首先看到题目想到的是生成一个从少到大的全排列的数组,然后再遍历数组得到对应的序号(数组下标加1),又或者想到一个个从小到大的生成push进数组,然后判断该数是不是当前题目给的数,如果是的话要求的序号就是当前数组

  • 浅谈js中字符和数组一些基本算法题

    最近在刷 fcc的题,跟升级打怪一样,一关一关的过,还挺吸引我的.今天抽时间把 Basic Algorithm Scritping  这部分题做了,根据一些提示,还是比较简单的.有些题的处理方式 方法,我想值得借鉴.比如在项目中有时候要处理一个字符,如果想不到一些相关的方法,还挺费事的,所以,在此记录下来,如果以后遇到一些字符或者数组处理,可以来翻翻这篇文章,希望以此得到一些提示而不是去翻文档. 看到此博文的博友,有更好更简单的代码或者好的想法,请留言交流(我一直觉得只有学习别人的优秀代码才能进

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

  • javascript常用经典算法实例详解

    javascript常用经典算法实例详解

    本文实例讲述了javascript常用算法.分享给大家供大家参考,具体如下: 入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld //线性搜索(入门HelloWorld) //A为数组,x为要搜索的值 function linearSearch(A, x) { for (var i = 0; i < A.length; i++) { if (A[i] == x) { return i; } } return -1; } 二分查找(又称折半查找) - 适用于已排好序的

  • 面试常见的js算法题

    我们去面试一般都有笔试,笔试题一般都会涉及到很多算法的东西. 不管你用的多不多,反正就是要会.不然笔试很难过. 就算是直接面试的,有时候也会遇到面试官直接叫你当场写个算法题出来这种情况. 因为笔试时间很有限,不会出很复杂的题目,所以笔试怎么出都不会离开下面这几种题. 废话不多说,下面来列出主要的几个算法题. 1.排序 一般都是给个数组然后排序,有的从小到大,有的从大到小.一定要看清楚.以下都是从小到大的排序算法. 冒泡法 var arr = [3,6,1,2,5]; var temp; for(

  • js数组去重的5种算法实现

    1.遍历数组法 最简单的去重方法,实现思路:新建一新数组,遍历传入数组,值不在新数组就加入该新数组中:注意点:判断值是否在数组的方法"indexOf"是ECMAScript5 方法,IE8以下不支持,需多写一些兼容低版本浏览器代码,源码如下: // 最简单数组去重法 function unique1(array){ var n = []; //一个新的临时数组 //遍历当前数组 for(var i = 0; i < array.length; i++){ //如果当前数组的第i已

  • 一个简单的JavaScript 日期计算算法

    复制代码 代码如下: <script type="text/javascript"> var today=new Date(); //定义当天日期对象 var year = today.getYear(); //获取年份 var month = today.getMonth(); //获取月份 var date = today.getDate(); //获取日期值 try{ //定义下个日期对象,日期值加上30天 var nextDay = new Date(year,mo

  • JavaScript生成GUID的多种算法小结

    全局唯一标识符(GUID,Globally Unique Identifier)也称作 UUID(Universally Unique IDentifier) . GUID是一种由算法生成的二进制长度为128位的数字标识符.GUID 的格式为"xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx",其中的 x 是 0-9 或 a-f 范围内的一个32位十六进制数.在理想情况下,任何计算机和计算机集群都不会生成两个相同的GUID. GUID 的总数达到了2^128(3

  • js交换排序 冒泡排序算法（Javascript版）

    比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. function sort(elements){ for(var i=0;i<elements.length-1;i++){ for(var j=0;j<elements.length-i-1;j++){ if(elemen

随机推荐