【剑指Offer】丑数

题目描述

将只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
考点：穷举

解题思路

丑数定义：一个丑数只包含质因子2、3、5，则丑数 UN = (2 ^ x) * (3 ^ y) * (5 ^ z)，即顺序（从小到大排序）靠后的某一个丑数一定是由顺序靠前的某一个丑数乘以质因子（2/3/5）获得。例如，已知1是第一个丑数，分别乘以2、3、5可得到2、3、5三个丑数，再将2、3、5这三个丑数分别乘以质因子2、3、5则可获得4、6、10、6、9、15、10、15、25九个丑数……显然，易发现此方法获取的丑数序列不仅得到重复丑数并且无序。因此，可以先列出三个队列如下操作（指针‘|’，丑数数组UN，其中UN[0] = 1）：

丑数数组：1
乘以2的队列：|2
乘以3的队列：|3
乘以5的队列：|5
目前三个序列的指针分别是0、0、0，三个入队元素值分别是UN[0] * 2 = 2、UN[0] * 3 = 3、UN[0] * 5 = 5，选取三个队列头部元素中最小值2进入丑数数组UN，将‘乘以2的队列’指针右移一位，同时将此最小值2乘以2、3、5分别对应放入三个队列中。
丑数数组：1 2
乘以2的队列：2 |4
乘以3的队列：|3 6
乘以5的队列：|5 10
目前三个序列的指针分别是1、0、0，三个队列头部元素值分别是UN[1] * 2 = 4、UN[0] * 3 = 3、UN[0] * 5 = 5，选取三个队列头部元素中最小值3进入丑数数组UN，将‘乘以3的队列’指针右移一位，同时将此最小值3乘以2、3、5分别对应放入三个队列中。
丑数数组：1 2 3
乘以2的队列：2 |4 6
乘以3的队列：3 |6 9
乘以5的队列：|5 10 15
目前三个序列的指针分别是1、1、0，三个队列头部元素值分别是UN[1] * 2 = 4、UN[1] * 3 = 6、UN[0] * 5 = 5，选取三个队列头部元素中最小值4进入丑数数组UN，将‘乘以2的队列’指针右移一位，同时将此最小值4乘以2、3、5分别对应放入三个队列中。
丑数数组：1 2 3 4
乘以2的队列：2 4 |6 8
乘以3的队列：3 |6 9 12
乘以5的队列：|5 10 15 20
目前三个序列的指针分别是2、1、0，三个队列头部元素值分别是UN[2] * 2 = 6、UN[1] * 3 = 6、UN[0] * 5 = 5，选取三个队列头部元素中最小值5进入丑数数组UN，将‘乘以5的队列’指针右移一位，同时将此最小值5乘以2、3、5分别对应放入三个队列中。
丑数数组：1 2 3 4 5
乘以2的队列：2 4 |6 8 10
乘以3的队列：3 |6 9 12 15
乘以5的队列：5 |10 15 20 25
目前三个序列的指针分别是2、1、1，三个队列头部元素值分别是UN[2] * 2 = 6、UN[1] * 3 = 6、UN[1] * 5 = 10，选取三个队列头部元素中最小值6进入丑数数组UN，将‘乘以2的队列’和‘乘以3的队列’指针都右移一位（因为这两个队列头部元素值均为最小值6），同时将此最小值6乘以2、3、5分别对应放入三个队列中。
丑数数组：1 2 3 4 5 6
乘以2的队列：2 4 6 |8 10 12
乘以3的队列：3 6 |9 12 15 18
乘以5的队列：5 |10 15 20 25 30
目前三个序列的指针分别是3、2、1，…………

C++11 (clang++ 3.9)

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index < 7) {  // 由分析可知从小到大的顺序中第i(i<7)个丑数是i
            return index;
        }
        int p2 = 0, p3 = 0, p5 = 0;  // p2、p3、p5分别是三个队列的指针
        int minNum = 1;  // minNum是三个队列头部元素中的最小值
        vector<int> UN;  // vector是一个能够存放任意类型的动态数组
        UN.push_back(minNum);  // 将minNum压入动态数组UN中，此时UN[0]=1
        while(UN.size() < index) { 
            minNum = min(UN[p2] * 2, min(UN[p3] * 3, UN[p5] * 5));  // 选取三个队列头部元素的最小值
            if(UN[p2] * 2 == minNum) p2++;  // 若最小值是‘乘以2的队列’头部元素，则此队列指针+1
            if(UN[p3] * 3 == minNum) p3++;  // 若最小值是‘乘以3的队列’头部元素，则此队列指针+1
            if(UN[p5] * 5 == minNum) p5++;  // 若最小值是‘乘以5的队列’头部元素，则此队列指针+1
            UN.push_back(minNum);  // 将选取的最小值minNum压入动态数组UN中
        }
        return minNum;
    }
};

2018校招真题（滴滴）—— 寻找丑数

题目描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
输入描述：整数N
输出描述：第N个丑数
示例：输入6 ——> 输出6

Java (javac 1.8)

import java.lang.Math;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    @SuppressWarnings("resource")
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            int index = input.nextInt();
            if (index < 7) {
                System.out.println(index);
            }
            else {
                int p2 = 0, p3 = 0, p5 = 0;
                int minNum = 1;
                ArrayList<Integer> UN = new ArrayList<Integer>();
                UN.add(minNum);
                while (UN.size() < index) {
                    minNum = Math.min(UN.get(p2) * 2, Math.min(UN.get(p3) * 3, UN.get(p5) * 5));
                    if (minNum == UN.get(p2) * 2) p2++;
                    if (minNum == UN.get(p3) * 3) p3++;
                    if (minNum == UN.get(p5) * 5) p5++;
                    UN.add(minNum);
                }
                System.out.println(minNum);
            }
        }
    }
}