剑指offer - 丑数(Java实现)

题目链接：https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&&tqId=11186&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先我们可以从 1 开始逐个的判断当前数字是否为丑数，直到我们找到第 n 个丑数为止，这样的方法在此题目中会造成时间超限，下面我把超时的方法贴在下面，在思路二中我将写出更快速的解法。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        int cnt = 0, number = 1;
        while(cnt < index) {
            if(isUglyNumber(number)) {
                ++ cnt;
            }
            ++ number;
        }
        return number - 1;
    }
    public static boolean isUglyNumber(int number) {
        while(number % 2 == 0) number /= 2;
        while(number % 3 == 0) number /= 3;
        while(number % 5 == 0) number /= 5;
        return number == 1 ? true : false;
    }
}

  思路二：既然直接判断每一个数是否为丑数这种方法行不通，那么我们就可以想是不是有一种方法可以让我们直接从某一个丑数直接得到下一个丑数的呢？实际上这种方法是可行的，首先我们知道 1 是一个丑数，那么我们从 1 可以推出 {2, 3, 5}，从 2 我们又可以推出 {4, 6, 10}，从 3 我们 可以推出 {6， 9， 15}。如果我们按照每一个丑数都乘以 {2, 3, 5} 来计算的话，我们可以得到所有的丑数，但是有一个问题，现在有很多重复的丑数，并且在计算的时候我们求出来的丑数也不是单调递增的，那么这个问题就转化为了我们如何得到一个单调递增的丑数序列，也就是说我们如果从当前的这个丑数推出来下一个丑数应该是什么？此时我们可以看下图的分析。

  现在我们的问题就是要记录当前最大的丑数的后一个值，所以我们设置三个指针，分别表示 2 的倍数，3 的倍数和 5 的倍数，一开始这个他们指向 2 3 5，一旦我们找到最小的以后，那么指向 2 的指针就指向 4，那么此时三个指针分别指向的数子 4 3 5，我们按照这个的规则，不断的找到最小的数字，不断的进行指针的后移，这样就可以以 的复杂度来解决这个问题。

import java.util.*;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index == 0) return 0;
        int[] ans = new int[index + 1];
        ans[1] = 1;
        int x = 1, y = 1, z = 1;
        for(int i = 2; i <= index; ++ i) {
            ans[i] = Math.min(ans[x] * 2, Math.min(ans[y] * 3, ans[z] * 5));
            if(ans[i] == ans[x] * 2) ++ x;
            if(ans[i] == ans[y] * 3) ++ y;
            if(ans[i] == ans[z] * 5) ++ z;
        }
        return ans[index];
    }
}