找到第n个自定义数
因为神奇数字做了相关的题目，个人建议做题顺序，从易到难
丑数【LC263】
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return true if n is an ugly number.
2022/11/22
- 思路：首先，0和负数一定不是丑数；当n是正数时，将n除以2、3、5直至除不尽，即有余数为止，若剩下的n为1，那么证明n可以转换为2、3、5的乘积，即为丑数
- 代码
class Solution { public boolean isUgly(int n) { if (n < 1){ return false; } while (n % 5 == 0){ n /= 5; } while (n % 3 == 0){ n /= 3; } while (n % 2 == 0){ n /= 2; } return n == 1; } }
。复杂度
- 时间复杂度：O(logn)，时间复杂度取决于对 n 除以 2,3,5的次数，由于每次至少将 n除以 2，因此除法运算的次数不会超过 O(logn)。
- 空间复杂度：O ( 1 )
丑数Ⅱ【LC264】
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
优先队列
- 思路：对于对于任意一个丑数 x，其与任意的质因数（2、3、5）相乘，结果（2x、3x、5x）仍为丑数。因此可以使用优先队列（小根堆）存放丑数x，每次从队列取出最小值x，并将x所对应的2x、3x和5x入队。第n次出队的值即为第n个丑数
- 实现：为了防止同一丑数多次进队，需要使用set来记录入过队列的丑数
class Solution { public int nthUglyNumber(int n) { int[] factors = {2, 3, 5}; Set<Long> seen = new HashSet<Long>(); PriorityQueue<Long> heap = new PriorityQueue<Long>(); seen.add(1L); heap.offer(1L); int ugly = 0; for (int i = 0; i < n; i++) { long curr = heap.poll(); ugly = (int) curr; for (int factor : factors) { long next = curr * factor; if (seen.add(next)) { heap.offer(next); } } } return ugly; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/ugly-number-ii/solutions/712102/chou-shu-ii-by-leetcode-solution-uoqd/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(nlogn)，从优先队列中取最小值为 O(1)，往优先队列中添加元素复杂度为O(logn)
- 空间复杂度：O(n)
多指针
- 思路：由于每个丑数都可以由比它小的丑数乘某一个质因数得到，因此可以使用三个指针来指向目标序列ans的某个下标，ans[指针]*质因数即代表该指针对应的质因数生成的新丑数的值，第idx个丑数值即为三个新丑数中的最小值
- 实现
class Solution { public int nthUglyNumber(int n) { // ans 用作存储已有丑数（从下标 1 开始存储，第一个丑数为 1） int[] ans = new int[n + 1]; ans[1] = 1; // 由于三个有序序列都是由「已有丑数」*「质因数」而来 // i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标（起始都指向 1） for (int i2 = 1, i3 = 1, i5 = 1, idx = 2; idx <= n; idx++) { // 由 ans[iX] * X 可得当前有序序列指向哪一位 int a = ans[i2] * 2, b = ans[i3] * 3, c = ans[i5] * 5; // 将三个有序序列中的最小一位存入「已有丑数」序列，并将其下标后移 int min = Math.min(a, Math.min(b, c)); // 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ） if (min == a) i2++; if (min == b) i3++; if (min == c) i5++; ans[idx] = min; } return ans[n]; } } 作者：宫水三叶 链接：https://leetcode.cn/problems/ugly-number-ii/solutions/714340/gong-shui-san-xie-yi-ti-shuang-jie-you-x-3nvs/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
超级丑数【LC313】
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
A super ugly number is a positive integer whose prime factors are in the array primes.
Given an integer n and an array of integers primes, return the nth super ugly number.
The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
2022/11/23
优先队列【超时】
- 思路：同丑数Ⅱ，但是超时
多指针
- 思路：同丑数Ⅱ，关键点在于每个丑数都可以由比它小的丑数乘某一个质因数得到
。同样使用长度为n+1的数组ans指向目标薛序列，ans[n]即为第n个超级丑数
。由于指针数量不确定，因此创建一个与primes数组长度m相等的指针数组ptr，ptr[i]代表第i个质因子指向的原超级丑数，那么该指针新生成的超级丑数为ans[ptr[i]]∗primes[i]
。第idx个丑数值即为m 个新超级丑数中的最小值min，并移动其对应的所有指针
- 错误做法：记录m 个新超级丑数中的最小值min，以及其对应的质因子的下标minPtr
生成的新超级丑数可能存在重复
- 代码
。使用动态数组ArrayList记录最小丑数对应的指针序号
。注意处理新超级丑数为负数的情况
class Solution { public int nthSuperUglyNumber(int n, int[] primes) { int[] ans = new int[n+1]; ans[1] = 1; int m = primes.length; int[] ptr = new int[m];// 记录每个质因数对应ans中的下标 Arrays.fill(ptr, 1); for (int idx = 2; idx <= n; idx++){ int min = Integer.MAX_VALUE; List<Integer> minPtrs = new ArrayList<>();// 记录最小丑数对应的ptr下标 for (int i = 0; i < m; i++){ int ugly = ans[ptr[i]] * primes[i]; if (ugly < 0){// 越界 continue; }else if (ugly < min){ min = ugly; minPtrs.clear(); minPtrs.add(i); }else if (ugly == min){ minPtrs.add(i); } } for (int minPtr : minPtrs){// 移动下标 ptr[minPtr]++; } ans[idx] = min; } return ans[n]; } }
。复杂度
- 时间复杂度：O(nm),n 为需要寻找的丑数编号，m为primes数组的长度
- 空间复杂度：O(n+m)
第N个神奇数字【LC878】
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
A positive integer is magical if it is divisible by either a or b.
Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.
找规律
2022/11/22
首先是我自己的暴力思路，当然没通过…但是可以结合官方题解2找规律一起看看
- 思路：根据题意，我们需要找到第n个能被a或者b整除的数。暴力判断1~n*min(a,b)内有多少个神奇数，必然超时。
如何优化搜索的过程？神奇数一定是a或者b的倍数，因此只需判断a和b的整数倍即可。从小到大搜索第count个神奇数[过了50个还是超时]
。首先考虑几种特殊情况，a为b的因数或者b为a的因数，此时第n个神奇数即为 n * 较小值
。然后使用两个指针记录curA、curB，记录a的整数倍和b的整数倍，并使用count计数
- 如果curA < curB，那么第count个神奇数为curA，移动curA
- 如果curA < curB，那么第count个神奇数为curA，移动curB
- 如果curA == curB，那么第count个神奇数为curA即curB，curA和curB在该值重合，需同时移动curA和curB，count只计一次数
- 代码
class Solution { public int nthMagicalNumber(int n, int a, int b) { int MOD = (int)1e9 + 7; if (a == b){ return (int)((long)n * a % MOD); }else if (a % b == 0){ return (int)((long)n * b % MOD); }else if (b % a == 0){ return (int)((long)n * a % MOD); } long count = 0; long curA = a; long curB = b; long res = 0; while (count < n){ if (curA < curB){// 此时第count个神奇数字是curA count++; res = curA; curA += a; }else if (curA > curB){// 此时第count个神奇数字是curB count++; res = curB; curB += b; }else {// curA和curB重合，计数，并同时移动curA和curB count++; res = curB; curA += a; curB += b; } } return (int)(res % MOD); } }
。复杂度
- 时间复杂度：O(nm)，m为min(a,b)
- 空间复杂度：O(1)
- 找规律，再次优化搜索过程。
。设f(x)为小于等于x的神奇数个数，c为a和b的最小公倍数，那么
。令小于等于c的神奇数个数m=f(c)
。由于最终结果res一定是最小公倍数c的整数倍或者其的后几个数，因此res=c∗q+num
。因为不大于c∗q 的「神奇数字」个数为m∗q，所以我们只需要从c∗q往后搜第 r个「神奇数字」即可。
所以n 可以由m 表示，n=q∗m+r,其中0 ≤ r < m ，q 为非负整数
- 如果r==0，那么c∗(n/m)即为结果
- 如果r!=0，那么从res往后搜索r次即可
class Solution { static final int MOD = 1000000007; public int nthMagicalNumber(int n, int a, int b) { int c = lcm(a, b); int m = c / a + c / b - 1; int r = n % m; int res = (int) ((long) c * (n / m) % MOD); if (r == 0) { return res; } int addA = a, addB = b; for (int i = 0; i < r - 1; ++i) { if (addA < addB) { addA += a; } else { addB += b; } } return (res + Math.min(addA, addB) % MOD) % MOD; } public int lcm(int a, int b) { return a * b / gcd(a, b); } public int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/nth-magical-number/solutions/1983699/di-n-ge-shen-qi-shu-zi-by-leetcode-solut-6vyy/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(a+b)
- 空间复杂度：O(1)
二分查找+数学
- 思路：将问题**“第n个神奇数是x”转化为“小于等于x的神奇数有n个”**，由于x越大n一定越大，因此可以使用二分法查找一个神奇数小于等于n的区间(0,right]，最后返回右边界
- 实现
。计算区间内的神奇数个数：假设该区间内能被a整除的数的个数为n a个，能被b整除的数的个数为n b个，能同时被a和被b整除的数的个数为n c 个，那么神奇数个数为n a + n b − n c
。n a 和n b的计算方法较简单：除法运算向下取整即可
。n c =该区间内能被a和b的最小公倍数整除的个数
- 最小公倍数可以使用最小公约数gcd得到
- 最小公约数用辗转相除法得到
。实现
class Solution { private static final long MOD = (long) 1e9 + 7; public int nthMagicalNumber(int n, int a, int b) { long lcm = a / gcd(a, b) * b; long left = 0, right = (long) Math.max(a, b) * n; // 开区间 (left, right) while (left + 1 < right) { // 开区间不为空 long mid = left + (right - left) / 2; if (mid / a + mid / b - mid / lcm >= n)// 神奇数个数大于等于n right = mid; // 范围缩小到 (left, mid) else// 神奇数个数小于n left = mid; // 范围缩小到 (mid, right) } return (int) (right % MOD); } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/nth-magical-number/solutions/1984641/er-fen-da-an-rong-chi-yuan-li-by-endless-9j34/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(nlog(m)，m为min(a,b)
- 空间复杂度：O ( 1 )
丑数Ⅲ【LC1201】
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数 。
二分查找+数学
神奇数字的升级版，需要考虑三个因子
- 思路：将问题**“第n个丑数是x”转化为“小于等于x的丑数有n个”**，由于x越大n一定越大，因此可以使用二分法查找一个丑数个数小于等于n的区间(0,right]，最后返回右边界
- 实现
。计算区间内的丑数个数【容斥原理】：该区间内能被a整除的数的个数为n a 个+能被b整除的数的个数为n b 个+能被c整除的数的个数为n c 个-a和b中重复的个数n a b -a和c中重复的个数n a c -b和c中重复的个数n b c +三个区间都重复的个数n a b c
。n a 、n b 、n c 的计算方法较简单：除法运算向下取整即可
。重叠部分的个数为区间内能被a和b的最小公倍数整除的个数
- 最小公倍数可以使用最小公约数gcd得到
- 最小公约数用辗转相除法得到
class Solution { public int nthUglyNumber(int n, int a, int b, int c) { long lcmAb = lcm(a, b); long lcmAc = lcm(a, c); long lcmBc = lcm(b, c); long lcmAbc = lcm(lcmAb,c); int min = Math.min(a, Math.min(b, c)); long l = 0, r = min * 1L * n ;//左开右开 while (l + 1 < r){ long mid = l + r >> 1; long count = mid / a + mid / b + mid / c - mid / lcmAb - mid / lcmAc - mid / lcmBc + mid / lcmAbc; if (count >= n){ r = mid; }else{ l = mid; } } return (int)r; } public long gcd(long a, long b){ return b == 0 ? a : gcd(b, a % b); } public long lcm(long a, long b){ return a * b / gcd(a, b); } }
总结
- 题型总结
。丑数和丑数Ⅱ：质因数只能包含2、3或5
。超级丑数：质因数只能出现在primes数组中
。神奇数：能被a或者b整除，因数除了a和b外还可以有其他数
。丑数Ⅲ：能被a或者b或者c整除，因数除了a、b和c外还可以有其他数
- 超级丑数为丑数Ⅱ的升级版，都可以使用多指针的思想解决
- 丑数Ⅲ为神奇数的升级版，可以使用二分查找和容斥原理解决，应该不会变态到把因数放到数组里吧，那就要定义数组存储每两个因数的最小公倍数、每三个因数的最小公倍数……
