快捷導(dǎo)航

javascript算法題：求任意一個(gè)1-9位不重復(fù)的N位數(shù)在該組合中的大小排列序號

更新時(shí)間：2015年04月01日 14:51:56 投稿：mdxy-dxy

這篇文章主要介紹了javascript算法題：求任意一個(gè)1-9位不重復(fù)的N位數(shù)在該組合中的大小排列序號,需要的朋友可以參考下

具體題目是這樣的：

　　從1--9中選取N個(gè)數(shù)字，組成不重復(fù)的N位數(shù)，從小到大進(jìn)行編號，當(dāng)輸入其中任何一個(gè)數(shù)M時(shí)，能找出該數(shù)字對應(yīng)

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

　　首先看到題目想到的是生成一個(gè)從少到大的全排列的數(shù)組，然后再遍歷數(shù)組得到對應(yīng)的序號(數(shù)組下標(biāo)加1)，又或者想到一個(gè)個(gè)從小到大的生成push進(jìn)數(shù)組，然后判斷該數(shù)是不是當(dāng)前題目給的數(shù)，如果是的話要求的序號就是當(dāng)前數(shù)組的長度，比前面好的一點(diǎn)的是不用浪費(fèi)時(shí)間去計(jì)算生成后面的項(xiàng)。生成本身復(fù)雜度不高，如果擴(kuò)展到16進(jìn)制甚至36進(jìn)制且給一個(gè)很大的數(shù)的話就不好了，還有需要浪費(fèi)一部分空間去保存用不上的數(shù)據(jù)?；蛟S我們可以嘗試其它不用生成的方法。

　　我們先理想化下題目，如果給了一個(gè)數(shù)N，那么，M就由1-N N位數(shù)組成（比如N=4,那M就由1234幾個(gè)數(shù)字組合，而不是其它1349等其它組合）。之所以這么做是因?yàn)槲覀円喕瘲l件好分析出共性得到解題的方法，而且要從隨機(jī)的情況轉(zhuǎn)化成理想的情況也不難，本文就不啰嗦了。先分析下題目給的例子，[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)] 213在第三位，首數(shù)字是2，也就是說首數(shù)字是1的都在他前面(123,132)，再來看第二個(gè)數(shù)字和后面的數(shù)的組合13，首字母1已經(jīng)是最小的了，他前面不可能有任何數(shù)，而第三個(gè)數(shù)字3就不用看了，因?yàn)槿绻懊娴奈粩?shù)都確定了，最后一位就只有一種可能了，得出來的結(jié)果就是213的前面有2(首位)+0(二位)+0(尾位)=2個(gè)數(shù)，也就是說當(dāng)前數(shù)在第3位，對比一下答案確實(shí)是這樣的，其它數(shù)的分析也一樣。由此可以得出我們要一個(gè)函數(shù)(也就是下面代碼的setAll())可以算出某一位比當(dāng)前數(shù)小的可能性總數(shù)，然后累加起來+1就是想要的結(jié)果，請看代碼實(shí)現(xiàn)：

//函數(shù)功能:得到每一位，如果是其它數(shù)的話比當(dāng)前小的可能性總數(shù)
//a  當(dāng)前數(shù)序號（從小到大）
//n  當(dāng)前數(shù)總數(shù)
function getAll(a,n){
 var sum=1; //總數(shù)
 for(var i=n;i>1;i--)sum=sum*i; //算出n個(gè)有序的位置放n個(gè)不同的數(shù)字的可能性總數(shù)
 return sum*(a-1)/n; //算出比首位為a的比當(dāng)前數(shù)小的數(shù)的可能性總數(shù)
}

//m 要計(jì)算的數(shù)序列
//a 存放當(dāng)前位的數(shù)在和它后位的數(shù)而組成的數(shù)它的大小序號
//  比如 213 的 a數(shù)組為 [2,1,1]; a[0]為2是因?yàn)?213 首位2在213三個(gè)數(shù)字中排第2小;而a[1]為1是因?yàn)?3的首位1在13中排第一小
function find(m){
 m=(m+"").split(""); //把當(dāng)前數(shù)拆分放在數(shù)組里面好方便對每一位進(jìn)行計(jì)算
 var a=new Array(m.length+1).join(1).split(""); //快速生成長度為m的長度的值都為1的數(shù)組，a數(shù)組的功能說明看上面函數(shù)頭的注釋
 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數(shù)組
 console.log("a數(shù)組：",a);
 for(i=1,sum=1;i<m.length;i++){
 sum+=getAll(+a[i-1],m.length-i+1); //循環(huán)調(diào)用getAll計(jì)算每一位與其后面的數(shù)成的組合比當(dāng)前組合小的可能性總數(shù)
 }
 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

您可能感興趣的文章: