剑指offer面试题系列

题目

我们把只包含因子2、3、5的数成为丑数，求按从小到大的顺序的第 1500 个丑数。习惯上我们把 1 当成第一个丑数。

思路

方法一：

让循环一直继续，直到找到第 1500 个丑数。这种方法的思路就是对于从 1 开始的每一个数都检验是不是丑数。所以时间耗费较大。

可以看出来，这种方法耗费了将近2分钟的时间。

方法二：

在第一种方法的基础上进行了改进，改善时间复杂度除了改变本身算法之外，另外一个最常用的方法就是以空间换取时间。

用一个数组保存已经遍历到的丑数。

解决此问题的关键所在就是利用到了一条规律：丑数的2、3、5倍还是丑数。

假设数组 a 中存放的都是之前遍历到的丑数，且已经排好序，最大值为 M。

可以想到如果给这个数组的每一个元素都分别乘以2、3、5，则产生的又会是新的丑数，但是有一点要注意：如果新的丑数小于M，则舍弃，因为这种丑数必然已经在 a数组中了。

怎么样来保证数组一直是排好序的呢？

通过比较来得出在 M 后面的下一个最小的丑数。就像代码中所示的那样，通过比较数组中的数字乘以 2、3、5 得到的结果，来得到最小的数字，然后排到数组 a 中。

以此类推，直到数组a的元素个数已经达到 1500 个。

比如 数组a中存放 1，2两个元素， M = 2。

乘以 2： 2，4 （2 <= M,意味着数组a中已经有了，舍去）

乘以 3：3，6

乘以5： 5，10

通过比较得出下一个元素是：3.

这种以空间来换取时间的方式大幅减小了程序运行所耗费的时间。

不到0.1秒。性能得到了很大的改善。

而空间只占用了 6KB.

代码

code1

package com.ans;

//find ugly numnber
public class Solution2 {
    // 输入序号，表示要寻找第几个丑数
    public static int findUglyNum(int seq) {
        int i = 2;
        int count = 1;
        int retVal = 1;
        while (true) {
            if (FenJie(i)) { // 前提条件
                // 测试还有没有其他的因子
                count++;
                System.out.println("丑数：" + i + ",序号: " + count);
                if (count == seq) {
                    retVal = i;
                    break;
                }
                i++;
            } else {
                i++;
            }

        }
        return retVal;
    }

    public static boolean FenJie(int num) {
        boolean flag = false;
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }

        while (num % 5 == 0) {
            num /= 5;
        }

        if (num == 1) {
            flag = true;
        }

        return flag;
    }



    public static void main(String[] args) {
        int N = 1500;
        System.out.println("程序开始运行");
        long startTime = System.currentTimeMillis();
        //System.out.println("第" + N + "个丑数是：" + findUglyNum(N));
        System.out.println("第" + N + "个丑数是：" + getUglyNum(N));
        long endTime = System.currentTimeMillis(); // 获取结束时间
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
    }
}

code2

public static int getUglyNum(int seq) {
    int[] arr = new int[seq];
    arr[0] = 1;
    int M = 1;
    int M2 = 1;
    int M3 = 1;
    int M5 = 1;

    int index = 1;
    while (index < seq) {
        for (int i = 0; i < index; i++) {
            M2 = 2 * arr[i];
            if (M2 > M) {
                System.out.println("M2 " + M2);
                break;
            }
        }
        for (int i = 0; i < index; i++) {
            M3 = 3 * arr[i];
            if (M3 > M) {
                System.out.println("M3 " + M3);
                break;
            }
        }
        for (int i = 0; i < index; i++) {
            M5 = 5 * arr[i];
            if (M5 > M) {
                System.out.println("M5 " + M5);
                break;
            }
        }

        M = getMinNum(M2, M3, M5);
        arr[index++] = M;
        System.out.println("M value: " + M);
    }

    return arr[index - 1];
}

// 找出三个数中的最小数
public static int getMinNum(int num1, int num2, int num3) {
    int min = num1 < num2 ? num1 : num2;
    min = min < num3 ? min : num3;
    return min;
}

总结

当你实在没有办法通过改进算法来减小时间复杂度，不妨试试“以空间来换取时间”这种方式。