LeetCode Ugly Number II

本文主要是介绍LeetCode Ugly Number II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">题目：</span>

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.

分析：这道题最直观地想法是暴力查找，但不用想也知道会超时，于是我想能不能找到规律，就是从每个生成数的系数。但是很遗憾。 
于是想到后面的每个ugly数都是由前面的ugly数所产生的。那这样的话就构成了一个生成链。但是这里有个重要的问题就是，生成链必须是有序的。最开始想法是每添加一个元素就排序，但是也会TLE，后来发现，当我们生成x时，我们下个希望生成的数肯定是大于x的，那么就可以从前向后查找list，看当*2，*3，*5后生成的大于x的数中，找到最小值，然后将其添加到list中，然后更新cur。 
这里还有个trick，就是如果每次都从最开始搜索，其实是没有必要的，直接从上次结束的位置搜索即可，因为那个位置以前都肯定小于cur.

首先LZ想到的也是用暴力法来解决，但是这个方法明显不好用,一定会超时，然后就用了网上看到的某一个方法，而且LZ这里也学到了一点东西，就是java里的数组其实是可以用list来模拟的，也就是说如果想用数组的话，那么可以用list.add()来插入某个数，也可以用list.size()来得到这个list的大小(长度)，用list.get()来得到具体的某一个数，而且它也是按照类似于数组的下标一样来得到数字的。

import java.util.ArrayList;
import java.util.List;public class Ugly 
{public static int nthUglyNumber(int n) {List<Integer> list = new ArrayList<Integer>();list.add(1);int cur = 2;int i1= 0,i2 = 0,i3 = 0;int min1,min2,min3;while (list.size() < n){while(list.get(i1)*2<cur) i1++;min1 = list.get(i1)*2;System.out.println(min1);while(list.get(i2)*3<cur) i2++;min2 = list.get(i2)*3;System.out.println(min2);while(list.get(i3)*5<cur) i3++;min3 = list.get(i3)*5;System.out.println(min3);int next = min1<min2?min1:min2;next = next<min3?next:min3;cur = next+1;list.add(next);}return list.get(n-1);}public static void main(String args[]){System.out.println(nthUglyNumber(1600));}
}

这篇关于LeetCode Ugly Number II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---