1. 題目

請你幫忙設計一個程序，用來找出第 n 個丑數。

丑數是可以被 a 或 b 或 c 整除的 正整數。

示例 1： 輸入：n = 3, a = 2, b = 3, c = 5 輸出：4 解釋：丑數序列為 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 個是 4。示例 2： 輸入：n = 4, a = 2, b = 3, c = 4 輸出：6 解釋：丑數序列為 2, 3, 4, 6, 8, 9, 12... 其中第 4 個是 6。示例 3： 輸入：n = 5, a = 2, b = 11, c = 13 輸出：10 解釋：丑數序列為 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 個是 10。示例 4： 輸入：n = 1000000000, a = 2, b = 217983653, c = 336916467 輸出：1999999984提示： 1 <= n, a, b, c <= 10^9 1 <= a * b * c <= 10^18 本題結果在 [1, 2 * 10^9] 的范圍內

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/ugly-number-iii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 類似題目：
  LeetCode 263. 丑數 && 264. 丑數 II（DP）
  LeetCode 313. 超級丑數（動態規劃）
  程序員面試金典 - 面試題 17.09. 第 k 個數（set優先隊列/DP）

class Solution { public:long nthUglyNumber(long n, long a, long b, long c) {long long mid;long long lcm_ab = lcm(a,b);//ab的最大公約數 long long lcm_ac = lcm(a,c);// aclong long lcm_bc = lcm(b,c);// bclong long lcm_abc = lcm(a,lcm_bc);//abc的最大公約數 //一個周期內，abc的最大公約數假設為n，有多少個丑數？//是 a 的倍數的 n/a 個 減去重復的 case 4,6,7 case 1//是 b 的倍數的 n/b 個 減去重復的 case 4,5,7 case 2//是 c 的倍數的 n/c 個 減去重復的 case 5,6,7 case 3//是 ab 的倍數的 n/lcm_ab 個 減去重復的 case 7 case 4//是 bc 的倍數的 n/lcm_bc 個 減去重復的 case 7 case 5//是 ac 的倍數的 n/lcm_ac 個 減去重復的 case 7 case 6//是 abc 的倍數的 n/lcm_abc = 1 個 case 7//case1-7匯總：如下long long count = lcm_abc/a + lcm_abc/b + lcm_abc/c - lcm_abc/lcm_ab - lcm_abc/lcm_ac - lcm_abc/lcm_bc + 1;long long factor = n/count;//到lcm_abc處有count個丑數，n個丑數還需要幾倍long long rest = n%count;//剩余的個數long long ans = factor*lcm_abc;//在factor*lcm_abc處已經得到，還差rest個丑數if(rest > 0){long long l = 1, r = lcm_abc, mid;while(l <= r){mid = l+((r-l)>>1);count = mid/a + mid/b + mid/c - mid/lcm_ab - mid/lcm_ac - mid/lcm_bc + mid/lcm_abc;if(count >= rest)r = mid-1;else// if(count < rest)l = mid+1;}ans += l;}return ans;}long lcm(long a, long b)//最小公倍數{return a*b/gcd(a,b);}long gcd(long a, long b)//最大公約數{long r;while(b){r = a%b;a = b;b = r;}return a;} };

二分處還可以寫做：

while(l < r) {mid = l+((r-l)>>1);count = mid/a + mid/b + mid/c - mid/lcm_ab - mid/lcm_ac - mid/lcm_bc + mid/lcm_abc;if(count >= rest)//mid處可能是答案，因為最后如[1,2]取不到2，不能mid-1r = mid;else// if(count < rest)l = mid+1; }

0 ms 6 MB

總結

以上是生活随笔為你收集整理的LeetCode 1201. 丑数 III（最小公倍数+二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。