丑数

发表于 | 分类于 ，

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

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
public class Solution {

    public int GetUglyNumber_Solution(int index) {
        if(index <= 0) {
            return 0;
        }
        if(index <= 5) {
            return index;
        }
        int[] array = new int[index];
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 4;
        array[4] = 5;
         
        for(int i = 5;i < index; i++) {
            int min = 0;
            int min2 = 0, min3 = 0, min5 = 0;
            int temp = 0;
            //找到已知的丑数的2倍的数，且该数比已知最大丑数大。
            for(int j = 0; j < i; j++) {
                temp = array[j] * 2;
                if(temp > array[i-1]) {
                    min2 = temp;
                    break;
                }
            }
            //同上，3倍
            for(int j = 0;j < i; j++) {
                temp = array[j] * 3;
                if(temp > array[i-1]) {
                     min3 = temp;	
                     break;
                }
            }
            //同上，5倍
            for(int j = 0; j < i; j++) {
                temp = array[j] * 5;
                if(temp > array[i-1]){ 
                    min5 = temp;
                    break;
                }
            }
            min = Math.min(Math.min(min2, min3), min5);
            array[i] = min;           
        }
        return array[index-1];
    }
}