[LeetCode] 264. Ugly Number II

轉自LeetCode

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, and n does not exceed 1690.

<Solution>

263. Ugly Number 的衍生題

想法如下

• 所有的 ugly number 都是 2 or 3 or 5 的乘積

• ugly number 可以分解為下列三個 list

(1) 1x2，2x2，3x2，4x2......

(2) 1x3，2x3，3x3，4x3...... 

(3) 1x5，2x5，3x5，4x5...... 

• 下一個 ugly number 會是 min(L1*2, L2*3, L3*5)

• 綜合以上條件，可以推出在第 n 位的 ugly number 是多少

code 如下
c++

	class Solution {
	public:
	int nthUglyNumber(int n) {
	vector<int> ans(1, 1);
	int index_2 = 0, index_3 = 0, index_5 = 0;
	while(ans.size() < n) {
	int nextNum_2 = ans[index_2] * 2;
	int nextNum_3 = ans[index_3] * 3;
	int nextNum_5 = ans[index_5] * 5;
	int nextUgly = min(nextNum_2, min(nextNum_3, nextNum_5));
	if(nextUgly == nextNum_2) {
	++index_2;
	}
	if(nextUgly == nextNum_3) {
	++index_3;
	}
	if(nextUgly == nextNum_5) {
	++index_5;
	}
	ans.push_back(nextUgly);
	}
	return ans.back();
	}
	};

view raw uglyNumberII.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun nthUglyNumber(n: Int): Int {
	val ans = arrayListOf<Int>()
	var index2 = 0
	var index3 = 0
	var index5 = 0
	ans.add(1)
	var nextNum2: Int
	var nextNum3: Int
	var nextNum5: Int
	var nextUgly: Int
	while(ans.size < n) {
	nextNum2 = ans[index2] * 2
	nextNum3 = ans[index3] * 3
	nextNum5 = ans[index5] * 5
	nextUgly = Math.min(nextNum2, Math.min(nextNum3, nextNum5))
	if (nextUgly == nextNum2) {
	++index2
	}
	if (nextUgly == nextNum3) {
	++index3
	}
	if (nextUgly == nextNum5) {
	++index5
	}
	ans.add(nextUgly)
	}
	return ans.last()
	}
	}

view raw ugly_number_II.kt hosted with ❤ by GitHub