GeezerVison is showing github.com — CodingInterview/Solution49.java at master · legolas007/CodingInterview

Expand file tree

Solution49.java

Copy path

More file actions

42 lines (31 loc) · 1.01 KB

Copy path

42 lines (31 loc) · 1.01 KB

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

package com.usher.algorithm.offer;

/**

* @Author: Usher

* @Description:

* 丑数（只包含因子2,3,5的数）：如果一个数能被2整除，就连续除以2，

* 如果能被3整除就连续除以3，如果能被5整除就连续除以5，如果最后得到的是1，这个数就是丑数

public class Solution49 {

public int GetUglyNumber_Solution(int index) {

if (index <= 6)

return index;

//三个下标用于记录丑数的位置

int i2 = 0, i3 = 0, i5 = 0;

int[] f = new int[index];

//第一个丑数1

f[0] = 1;

for (int i =1;i < index;i++){

//三个数都是可能的丑数，取最小的放进丑数数组里面

int n2 = f[i2] * 2,n3 = f[i3] * 3,n5 = f[i5] * 5;

f[i] = Math.min(n2,Math.min(n3,n5));

if (f[i] == n2)

i2++;

if (f[i] == n3)

i3++;

if (f[i] == n5)

i5++;

}

return f[index-1];

}