首页 Algorithm

# 题目描述

设计一个算法，找出只含素因子 2 ， 3 ， 5 的第 n 小的数。

符合条件的数如： 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

我们可以认为 1 也是一个丑数。

要求时间复杂度为 O (nlogn) 或者 O (n)

# 问题分析

因子只含 2，3，5，那么必然是 1 乘以 2，3，5 得出的数再不断地乘以 2，3，5。但是这样得出的数是无序的，并且存在重复值的。那么这道题的难度就在于怎么取到第 n 小的数。

我们将获得的丑数放在一个 ArrayList 中，借用三个指针，p2，p3，p5，分别指向 list 的元素位置。每次都取 2*list.get (p2)，3*list.get (p3)，5*list.get (p5) 中最小的放进 list，最小的那个的元素指针向后移动一个位置，比如 2*list.get (p2)，则 p2+1。如此循环，直到将第 n 个数放入为止。

# 代码实现

public int nthUglyNumber(int n) {
    List<Integer> uglyNumbers = new ArrayList<>(n);
    uglyNumbers.add(1);
    int p2 = 0;
    int p3 = 0;
    int p5 = 0;
    for (int i = 1; i < n; i++) {
        Integer lastNumber = uglyNumbers.get(i - 1);
        while (uglyNumbers.get(p2) * 2 <= lastNumber) {
            p2++;
        }
        while (uglyNumbers.get(p3) * 3 <= lastNumber) {
            p3++;
        }
        while (uglyNumbers.get(p5) * 5 <= lastNumber) {
            p5++;
        }
        uglyNumbers.add(Math.min(Math.min(uglyNumbers.get(p2) * 2, uglyNumbers.get(p3) * 3), uglyNumbers.get(p5) * 5));
    }
    return uglyNumbers.get(n - 1);
}