LeetCode Ugly Number II

LeetCode Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

  1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
  2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
  3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
  4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

本题是LeetCode Ugly Number的升级版,题目还是不错的,要求出第n个丑数是什么。非常naive的方法就是从1开始不断调用LeetCode Ugly Number中判断丑数的函数,如果是丑数,cnt++,直到cnt==n时输出第n个丑数,但是hint里指出很多都不是丑数,所以这样很浪费时间。

hint里同时给出了怎样直接生成所有丑数序列的方法,不错。

主要思路是这样的,每个丑数都是更小的丑数乘以2,3或5得到的,所以我们可以维护一个丑数序列,要求更大的丑数时,用更小的丑数乘以2,3,5来得到,但是2,3,5对应的那个小丑数并不是一样的。举个例子,首先丑数序列中只有{1}这个元素,对于2,3,5,初始的时候i2=i3=i5=0,表明2,3,5对应丑数序列中的第0个元素1,此时用1分别乘以2,3,5得到的最小值是2,所以下一个丑数是1*2得到的,那么i2++去对应下一个小丑数,i3和i5对应的下标不变。不断这样产生丑数。

不太好描述,请看代码:

class Solution {
public:
	int nthUglyNumber(int n) {
		if (n == 1)return 1;
		vector<int> ugly_num = { 1 };
		int i2 = 0, i3 = 0, i5 = 0;
		int next_ugly_num = 0;
		while (ugly_num.size() < n) {
			next_ugly_num = min(min(ugly_num[i2] * 2, ugly_num[i3] * 3), ugly_num[i5] * 5);
			if (next_ugly_num == ugly_num[i2] * 2)i2++;
			if (next_ugly_num == ugly_num[i3] * 3)i3++;
			if (next_ugly_num == ugly_num[i5] * 5)i5++;
			ugly_num.push_back(next_ugly_num);
		}
		return next_ugly_num;
	}
};

代码很简洁,但是要想到这个思路还是有难度的。本代码提交AC,用时16MS。

One thought on “LeetCode Ugly Number II

  1. Pingback: LeetCode Super Ugly Number | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *