题目分析

非常有趣的一道题，看似简单，其实做起来很不容易想到最优的方法，我第一眼看上去就知道需要使用DP进行求解，然而提交时超出了时间限制，下面带小伙伴们看一看。

DP(超时)

第i个数是丑数的前提是，i除以2或i除以3或i除以5是丑数，于是可以从2开始遍历。2除以2等于1，是丑数，因此将2加入哈希表中，3除以3等于1，是丑数，因此将3加入哈希表中，4除以2等于2，是丑数，因此将4加入哈希表中，以此类推。

因为n较大时，这个数非常大，因此会TLE。

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = set()
        dp.add(1)
        current = 1
        while len(dp) < n:
            current += 1
            if current / 2 in dp or current / 3 in dp or current / 5 in dp:
                dp.add(current)
        return current

优化DP

上面的方法虽然可行，但是当n=1690时，第n个丑数为2123366400，超过了时间限制。我们需要找一种时间复杂度更小的算法。我们发现丑数除以2，除以3，除以5也都是丑数，因此我们只需要保存丑数序列即可，建立三个指针，都指向1，一个指针每次负责乘2，一个负责乘3，一个负责乘5，因为指针都是指向丑数，因此三个指针乘积结果最小的也就是当前的丑数。再比较这个数是由哪一个指针得到，说明这个指针应该相后移动一个距离，移到下一个可能产生丑数的地方。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        p2, p3, p5 = 0, 0, 0
        dp = [1] * n
        for i in range(1, n):
            mini = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
            if mini == dp[p2] * 2:
                p2 += 1
            if mini == dp[p3] * 3:
                p3 += 1
            if mini == dp[p5] * 5:
                p5 += 1
            dp[i] = mini
        return dp[-1]

堆

这个题目也可以使用最小堆来解决，我们每次取一个最小值k，cnt += 1，让k x 2，k x 3，k x 5的值都加入最小堆中，当cnt == k时，返回该值即可。

用哈希表存储最小堆中的值，有重复值时不用重复插入。

因为我们按照位来操作，因此算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$**。

import heapq


class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        visited = {1}
        heap = [1]
        cnt = 1
        while cnt != n:
            mini = heapq.heappop(heap)
            mini_2, mini_3, mini_5 = mini * 2, mini * 3, mini * 5
            if mini_2 not in visited:
                visited.add(mini_2)
                heapq.heappush(heap, mini_2)
            if mini_3 not in visited:
                visited.add(mini_3)
                heapq.heappush(heap, mini_3)
            if mini_5 not in visited:
                visited.add(mini_5)
                heapq.heappush(heap, mini_5)
            cnt += 1
        return heap[0]

刷题总结

丑数是不是非常有趣呢？这个题目的最优解是一个三指针加动态规划的问题，希望小伙伴可以喜欢。