leetcode-264-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.

Example:

1
2
3
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

  1. 1 is typically treated as an ugly number.
  2. n does not exceed 1690.

分析

ugle number 的序列中的 ugle number 总是可以由之前较小的一个 ugle number 乘以 2 或 3 或 5 得到。在题目的提示中也有：

1
Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

那么原序列可以分成三个子序列：

1
2
3
2=1✘2 4=2✘2 6=3✘2 8=4✘2 10=5✘2...
3=1✘3 6=2✘3 9=3✘3 12=4✘3 15=5✘3...
5=1✘5 10=2✘5 15=3✘5 20=4✘5 25=5✘5...

用三个变量维护这三个子序列的索引，每次根据三个索引值得到三个子序列中的最小的那个，当子序列的某个值加入到结果的序列中后，该子序列的索引值加一。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int nthUglyNumber(int n) {
        int multiply2 = 0, multiply3 = 0, multiply5 = 0;
        List<Integer> result = new ArrayList<Integer>();
        
        result.add(1);
        while(result.size() < n) {
            int newItem = Math.min(result.get(multiply2)*2, Math.min(result.get(multiply3)*3, result.get(multiply5)*5));
            result.add(newItem);
            if (result.get(multiply2) * 2 == newItem) {
                multiply2++;
            } 
            if (result.get(multiply3) * 3 == newItem) {
                multiply3++;
            }
            if (result.get(multiply5) * 5 == newItem) {
                multiply5++;
            }
        }
        return result.get(result.size()-1);
    }
}

相关问题

题目来源