Problem

Ugly number is a number that only have factors2,3and5.

Design an algorithm to find the_n_th ugly number. The first 10 ugly numbers are1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Notice

Note that1is typically treated as an ugly number.

Example

Ifn=9, return10.

思路一(暴力)

• 沿用ugly number I 的思路, 从1开始, 检验
• 时间复杂度O(N)

思路二(heap)

• 优化思路:
  • 思路一的N可能会很大很大, 因为有很多都不是ugly number
  • 2, 3, 5都是ugly number, 之后的ugly number都是基于前面的ugly number
  • 所以我们不需要去检验一堆数中哪些是ugly number, 而是去直接制造ugly number
  • 每次都输出最小的ugly number, 并用这个最小的number制造之后的number.
  • 所以我们需要使用heap
• 时间复杂度: O(nlogn)
• TreeSet

    public int nthUglyNumber2(int n) {
        TreeSet<Long> ans = new TreeSet<>();
        ans.add(1L);
        for (int i = 0; i < n - 1; ++i) {
            long first = ans.pollFirst();
            ans.add(first * 2);
            ans.add(first * 3);
            ans.add(first * 5);
        }
        return ans.first().intValue();
    }

• PriorityQueue + HashSet

    public int nthUglyNumber(int n) {
        HashSet<Long> hash = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.add(1L);
        hash.add(1L);

        for (int i = 0; i < n - 1; ++i) {
            long first = queue.poll();
            if (!hash.contains(first * 2)) {
                queue.add(first * 2);
                hash.add(first * 2);
            }
            if (!hash.contains(first * 3)) {
                queue.add(first * 3);
                hash.add(first * 3);
            }
            if (!hash.contains(first * 5)) {
                queue.add(first * 5);
                hash.add(first * 5);
            }
        }

        return queue.poll().intValue();
    }

思路三(ArrayList)

• 优化思路:
  • 时间复杂度只能是O(n)
• 保留一定顺序, 并且O(1)时间内能找到最小的元素, 集合大小不确定, 那么只能是ArrayList了.
• 维护三个index, 分别指向2, 3, 5所组成的最小元素, 然后比较得到最小的他们之中最小元素, 然后放在最后

    public int nthUglyNumber(int n) {
        if(n<=0) return 0;
        int a=0,b=0,c=0;
        List<Integer> table = new ArrayList<Integer>();
        table.add(1);
        while(table.size()<n)
        {
            int next_val = Math.min(table.get(a)*2,Math.min(table.get(b)*3,table.get(c)*5));
            table.add(next_val);
            if(table.get(a)*2==next_val) a++;
            if(table.get(b)*3==next_val) b++;
            if(table.get(c)*5==next_val) c++;
        }
        return table.get(table.size()-1);
    }