49.丑数
49.1 题目描述
面试题49. 丑数
我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/
49.2 解析
49.2.1 要做什么？
网上好多大神都有解析过这个问题，leetcode官网上的高赞回答look一下就大概知道该怎么做了。
大体是这样的：
由于丑数的独特性质，所以每个数都是之前的某个数的2倍或者3倍或者5倍。如果我们想求index位置上的数字，那么我们可以用三个指针，一个ptr2，一个ptr3，一个ptr5，分别指向×2，×3，×5刚好大于等于index位置的那些数。这么说还不太清楚，我们可以设几个变量。
假设这个数组是 arr，上述可以表示为
arr[ptr2] * 2 >= arr[index]
arr[ptr3] * 3 >= arr[index]
arr[ptr5] * 5 >= arr[index]
在这几个之中一定有等于 arr[index] 的，（假装没人发现我心虚了，强行解释😀），并且这几个都大于等于 arr[index]，说明等于 arr[index] 的一定是arr[ptr2] * 2、 arr[ptr3] * 3、 arr[ptr5] * 5 这三个里面最小的（不一定只有一个，比如6可以等于 3*2 也可以等于 2*3）。找到最小的值，把值赋给 arr[index] ，再将最小值对应的指针进行+1操作，后移一位。
我们先看看代码
public int nthUglyNumber(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] arr = new int[n];
int ptr2 = 0, ptr3 = 0, ptr5 = 0;
arr[0] = 1;
//对数组循环遍历
for (int i = 1; i < n; i++) {
int a = arr[ptr2] * 2;
int b = arr[ptr3] * 3;
int c = arr[ptr5] * 5;
//获得最小值并赋值给当前的数组元素
arr[i] = Math.min(a, Math.min(b, c));
//对产生最小值的指针后移一位
if (arr[i] == a) ptr2++;
if (arr[i] == b) ptr3++;
if (arr[i] == c) ptr5++;
}
return arr[n - 1];
}
49.2.2 为什么这么做？
这个动态规划问题很多情况下是可意会难言谈的东西，比如我为什么要用三个指针？为什么指针要加一？为什么这么做就行了？为什么为什么？感觉大佬做了一堆推理，数学公式，转移方程写了好多，知识就是不进脑子，我还是不知道为啥，也许是天生对这些东西有抵触情绪吧。
49.2.3 数学证明每一步的正确性
这里我们先假设每个元素都是已知的，比如前十个丑数：1，2，3，4，5，6，8，9，10，12，我们用这个构成一个数组testArr。
对于数组 testArr，我们从第二个数 2 开始遍历，为啥是第二个数？因为咱们不是要求每个数和前几个数的关系吗？你从第一个开始，就没必要找和之前的数的关系了。
从第二个数开始遍历，即index = 1，此时所有的 ptr 指针都指向第一个数 —— testArray[0]
此时：
ptr2 = 0, ptr3 = 0, ptr5 = 0, index = 1
testArr[ptr2] * 2 = 1 * 2 = 2 >= testArr[index]testArr[ptr3] * 3 = 1 * 3 = 3 >= testArr[index]testArr[ptr5] * 5 = 1 * 5 = 5 >= testArr[index]
一个基本前提：你要求的每个丑数，都一定是之前的某个丑数的2、3或者5倍
此时我们要提出一个中心思想: 每个指针指向的丑数，乘以指针对应的因数后恰好大于等于我们所要求的丑数
明确指针的含义: ptr2指向乘以2后恰好>=所求丑数的丑数，ptr3指向乘以3后恰好>=所求丑数的丑数， ptr5指向乘以5后恰好>=所求丑数的丑数
我们接下来要做的，就是小心翼翼滴去维护这个状态，只有这样，我们才能通过最小的值来求出所要求得的丑数。就比如，我们的index指针后移一位：
如上图，这几个问号都是什么关系呢？
证明一
用数学语言来解释就是：
易知：
testArr[index+1] > testArr[index]
∵
testArr[ptr2] * 2 == testArr[index]
∴
testArr[index + 1] > testArr[ptr2] * 2①
∵
testArr[ptr3]是丑数 ＆testArr[ptr3] × 3>testArr[index]
∴
testArr[ptr3] × 3一定是testArr[index]后面的某个丑数
∴
testArr[ptr3] × 3≥testArr[index + 1]②
同理：
testArr[ptr5] × 5≥testArr[index + 1]
所以通过①，我们证明了每次要把使得testArr[ptr~] = testArr[index]的这个ptr指针加一。比如testArr[ptr2] == testArr[index]，那么testArr[ptr2] < testArr[index + 1]，testArr[ptr2 + 1] >= testArr[index + 1];
通过②，我们可以证明，其余的指针不需要处理。
证明二
在走下一步之前我们要考虑另一个问题？你咋知道testArr[ptr2]、testArr[ptr3]、testArr[ptr5]之中一定有一个数等于 testArr[index]?
困 难 的 问 题 增 加 了。
不过还是可以证明一下的，这里你发现了没，我们认为的情况是，存在一个数能怎么怎么滴的，你想问会不会存在一种情况使得他所有的数都不能这么滴，所以我们对这种情况可以采用 反证法。
比如我们到了如下的情况(别看数字，忘记具体数字，我们现在在搞证明)
在不看数据的情况下，你能保证testArr[ptr2]、testArr[ptr3]、testArr[ptr5]之中一定有一个数等于 testArr[index]吗？
开始操作：
假设 所有的
testArr[ptr]都大于testArr[index]（一定是大于，不可能小于，可以参照上面的证明）
那么 一定存在一个
ptrX小于ptr2、ptr3、ptr5，使得testArr[ptrX] × X == testArr[index]
∵ 我们的移动规则是 只有当
testArr[ptr] == testArr[index]时，ptr后移一位
∴ 对于之前任意的
index' < index,testArr[ptrX] > testArr[index'], 都不可能使得ptrX向后移动，那么也就是说一定有一个指针一直停留在ptr2、ptr3、ptr5之前……
停，我们总共就三个指针，不可能有指针停留在ptr2、ptr3、ptr5之前，所以推导出矛盾，证明三个指针中一定有testArr[ptr] == testArr[index]
通过证明一和证明二，我们终于可以确信，自己可以每次从testArr[ptr2]、testArr[ptr3]、testArr[ptr5]中获得 testArr[index] 这个丑数。再次看看代码
public int nthUglyNumber(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] arr = new int[n];
int ptr2 = 0, ptr3 = 0, ptr5 = 0;
arr[0] = 1;
//对数组循环遍历
for (int i = 1; i < n; i++) {
int a = arr[ptr2] * 2;
int b = arr[ptr3] * 3;
int c = arr[ptr5] * 5;
//获得最小值并赋值给当前的数组元素
arr[i] = Math.min(a, Math.min(b, c));
//对产生最小值的指针后移一位
if (arr[i] == a) ptr2++;
if (arr[i] == b) ptr3++;
if (arr[i] == c) ptr5++;
}
return arr[n - 1];
}
-
定义三个指针
-
找到三个指针指向的数乘以对应因数的最小值并赋值给相应的位置的丑数
-
指向最小值的指针后移一位
-
继续循环
49.x 结尾彩蛋
我们可以通过一段代码来感知一下（代码可以跳过）。
public static void main(String[] args) {
int[] testArr = new int[]{
1, 2, 3, 4, 5, 6, 8, 9, 10, 12};
int ptr2Number = 0;
int ptr3Number = 0;
int ptr5Number = 0;
int ptr2 = 0;
int ptr3 = 0;
int ptr5 = 0;
for (int i = 1; i < 10; i++) {
System.out.println("现在运行到了第"+ (i + 1) + "个元素" + testArr[i]);
System.out.println();
System.out.println("开始从头找 X × 2 ≥ testArr[" + i + "] 的X：");
for (int j = 0; j < i; j++) {
System.out.println("testArr[" + j + "] = " + testArr[j]);
System.out.println("testArr[" + j + "] × 2 = " + testArr[j] * 2);
if (testArr[j] * 2 >= testArr[i]) {
System.out.println("符合大于等于的要求");
if (testArr[j] * 2 == testArr[i]) {
ptr2 = j + 1;
System.out.println("testArr[" + j + "] * 2 == " + testArr[i] + " ptr2指向下一位——>" + ptr2);
}
ptr2Number++;
break;
} else {
System.out.println("不符合要求");
}
}
System.out.println();
System.out.println("开始从头找 X × 3 ≥ testArr[" + i + "] 的X：");
for (int k = 0; k < i; k++) {
System.out.println("testArr[" + k + "] = " + testArr[k]);
System.out.println("testArr[" + k + "] × 3 = " + testArr[k] * 3);
if (testArr[k] * 3 >= testArr[i]) {
System.out.println("符合大于等于的要求");
if (testArr[k] * 3 == testArr[i]) {
ptr3 = k + 1;
System.out.println("testArr[" + k + "] * 3 == " + testArr[i] + " ptr3指向下一位——>" + ptr3);
}
ptr3Number++;
break;
} else {
System.out.println("不符合要求");
}
}
System.out.println();
System.out.println("开始从头找 X × 5 ≥ testArr[" + i + "] 的X：");
for (int k = 0; k < i; k++) {
System.out.println("testArr[" + k + "] = " + testArr[k]);
System.out.println("testArr[" + k + "] * 5 = " + testArr[k] * 5);
if (testArr[k] * 5 >= testArr[i]) {
System.out.println("符合大于等于的要求");
if (testArr[k] * 5 == testArr[i]) {
ptr5 = k + 1;
System.out.println("testArr[" + k + "] * 5 == " + testArr[i] + " ptr5指向下一位——>" + ptr5);
}
ptr5Number++;
break;
} else {
System.out.println("不符合要求");
}
}
System.out.println("ptr2 ——> " + ptr2 + "; ptr3 ——> " + ptr3 + "; ptr5 ——> " + ptr5);
System.out.println("-----------------------------------------------------------------------------------");
System.out.println("-----------------------------------------------------------------------------------");
System.out.println("-----------------------------------------------------------------------------------");
}
}
别害怕。做这么多，只是想看看这个过程到底是什么样子的，这是对前十个丑数进行处理得到的，我们想看的是这三个指针是怎么变化以及为何如此变化。
下面是结果（只截取了前四个）
现在运行到了第2个元素2
开始从头找 X × 2 ≥ testArr[1] 的X：
testArr[0] = 1
testArr[0] × 2 = 2
符合大于等于的要求
testArr[0] * 2 == 2 ptr2指向下一位——>1
开始从头找 X × 3 ≥ testArr[1] 的X：
testArr[0] = 1
testArr[0] × 3 = 3
符合大于等于的要求
开始从头找 X × 5 ≥ testArr[1] 的X：
testArr[0] = 1
testArr[0] * 5 = 5
符合大于等于的要求
ptr2 ——> 1; ptr3 ——> 0; ptr5 ——> 0
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
现在运行到了第3个元素3
开始从头找 X × 2 ≥ testArr[2] 的X：
testArr[0] = 1
testArr[0] × 2 = 2
不符合要求
testArr[1] = 2
testArr[1] × 2 = 4
符合大于等于的要求
开始从头找 X × 3 ≥ testArr[2] 的X：
testArr[0] = 1
testArr[0] × 3 = 3
符合大于等于的要求
testArr[0] * 3 == 3 ptr3指向下一位——>1
开始从头找 X × 5 ≥ testArr[2] 的X：
testArr[0] = 1
testArr[0] * 5 = 5
符合大于等于的要求
ptr2 ——> 1; ptr3 ——> 1; ptr5 ——> 0
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
现在运行到了第4个元素4
开始从头找 X × 2 ≥ testArr[3] 的X：
testArr[0] = 1
testArr[0] × 2 = 2
不符合要求
testArr[1] = 2
testArr[1] × 2 = 4
符合大于等于的要求
testArr[1] * 2 == 4 ptr2指向下一位——>2
开始从头找 X × 3 ≥ testArr[3] 的X：
testArr[0] = 1
testArr[0] × 3 = 3
不符合要求
testArr[1] = 2
testArr[1] × 3 = 6
符合大于等于的要求
开始从头找 X × 5 ≥ testArr[3] 的X：
testArr[0] = 1
testArr[0] * 5 = 5
符合大于等于的要求
ptr2 ——> 2; ptr3 ——> 1; ptr5 ——> 0
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
京公网安备 11010502036488号