讨论/题目交流/🏆 第 155 场力扣周赛/
🏆 第 155 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。
image.png

展开讨论

丑数用的二分查找大法
首先计算各种最小公倍数,然后用二分查找发现是否存在一个数k,使小于等于k的丑数个数是n

class Solution {
    private long gcd(long a, long b){
        long x;
        x = a % b;
        while(x!=0){
            a = b;
            b = x;
            x = a % b;
        }
        return b;
    }
    private long getUglyNumberNums(long k, long a, long b, long c, long ab, long bc, long ac, long abc){// 增函数
        long an = k/a, bn = k/b, cn = k/c, abn = k / ab, bcn = k / bc, acn = k / ac, abcn = k / abc;
        return an + bn + cn - abn - bcn - acn + abcn;
    }
    public int nthUglyNumber(long n, long a, long b, long c) {
        long ab, bc, ac, abc, t;
        long res=0,l,r;
        t = 0;
        ab = gcd(a,b);
        bc = gcd(b,c);
        ac = gcd(a,c);
        // 最小公倍数
        ab = a*b/ab;
        bc = b*c/bc;
        ac = a*c/ac;
        abc = ab*bc/gcd(ab,bc);
        l = 1;r = 2000000000;
        while(l<=r&&t!=n){
            res = (l+r)/2;
            t = getUglyNumberNums(res,a,b,c,ab,bc,ac,abc);
            if(t<n) l = res + 1;
            else if(t==n) break;
            else r = res - 1;
        }
        while(res%a!=0&&res%b!=0&&res%c!=0) res--;  // 往下找最后一个丑数
        return (int)res;
    }
}
2
展开全部 14 讨论