今天做了丑数2，遇到个坑，卡主自己好久，所以make先，以后有空再仔细研究
先上题目：1
2
3
4
5
6
7
8
9
10
11
12
13Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.
先给出我最终通过的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45var nthUglyNumber = function(n) {
//debugger
var arry = []
var arry_two = [2]
var i = 0
var arry_three = [3]
var j = 0
var arry_five = [5]
var k = 0
var a = arry_two[i]
var b = arry_three[i]
var c = arry_five[i]
if (n < 5) {
return n
}
while (1) {
if ( a < b && a < c) {
arry_two.push(a * 2)
arry_three.push(a * 3)
arry_five.push(a * 5)
arry.push(a)
a = arry_two[i += 1]
} else if(b < a && b < c ) {
arry_three.push(b * 3)
arry_five.push(b * 5)
arry.push(b)
b = arry_three[j += 1]
} else if (c < a && c < b) {
arry_five.push(c * 5)
arry.push(c)
c = arry_five[k += 1]
}
if(arry.length + 1 === n) break
}
//console.log(arry)
return arry[n - 2] //减去 0和 1
};
//console.log(nthUglyNumber(5))
现在来分析一下解决这个题目的思路：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26丑数就是只由2 3 5 乘出来的数字，我们定义三个数组，我们每次三个数组最小的数字，在第一组就分别乘以 2 3 5 放入 三个数组
arry_two 2
arry_three 3
arry_five 5
arry_two 2 4
arry_three 3 6
arry_five 5 10
然后我们把最小的取出来
arry_two x 4
arry_three 3 6
arry_five 5 10
此时最小的是3，他位于第二个数组，我们给他 乘以3和5分别放入第二个和第三个数组
arry_two x 4
arry_three 3 6 9
arry_five 5 10 15
我们去出3，此时最小的是4，4 位于第一个数组，我们乘以2 3 5 后分别放入三个数组
arry_two x 4 8
arry_three x 6 9 12
arry_five 5 10 15 20
我们拿去4 后最小的是5，然后我们 给5 乘以5放入第三个数组
arry_two x x 8
arry_three x 6 9 12
arry_five 5 10 15 20 25
然后我们把每次拿出来的数字，放到一个数组，就是从2开始的丑数啦
在再放出我一开始的问题程序：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64var nthUglyNumber = function(n) {
//debugger
var ff = n
n = n + 150
var count = 4 //1也是丑数
var arry = []
var arry_temp = []
var arry_two = [2]
var i = 0
var arry_three = [3]
var j = 0
var arry_five = [5]
var k = 0
var a = arry_two[i]
var b = arry_three[i]
var c = arry_five[i]
if (ff < 5) {
return ff
}
while (1) {
if ( a < b && a < c) {
arry_two.push(a * 2)
count++
if(count === n) break
arry_three.push(a * 3)
count++
if(count === n) break
arry_five.push(a * 5)
count++
if(count === n) break
a = arry_two[i += 1]
} else if(b < a && b < c ) {
arry_three.push(b * 3)
count++
if(count === n) break
arry_five.push(b * 5)
count++
if(count === n) break
b = arry_three[j += 1]
} else if (c < a && c < b) {
arry_five.push(c * 5)
count++
if(count === n) break
c = arry_five[k += 1]
}
}
arry_temp = arry_two.concat(arry_three)
arry = arry_temp.concat(arry_five)
function sortNumber(a,b){
return a - b
}
arry.sort(sortNumber)
//console.log(arry)
return arry[n - 152] //多算了x个 减去 0和 1
};
这个程序的思路没有放在取出来的丑数上，而是放在了求出来的丑数上，我计算出目前算了多少个丑数，比如要10个我就计算10个，结果发现求出来的并没有按顺序（中间有空缺），比如算10个丑数，其实只计算到了15，计算第11个丑数的时候才把12计算出来，当时头脑一发热，好不是少计算了，那我多计算好了，所以我们多计算150个，结果在1 和 1690 的时候都对，在(1406,1430)之间不对，其余数字都对，真让人心累，为什么出现这样情况，现在头脑不清楚，有空好好进去瞅瞅，应该还是少计算的原因，不过比他大的数字都是好的，这个就很奇怪了，不过就算这个可以通过测试，比如我多计算500个或者600个。这个思路都是有问题的，不是好思路。
