LeetCode 1224

鏈接：https://leetcode.com/problems/maximum-equal-frequency/

方法：

時間復(fù)雜度：O(n)
想法：我當(dāng)時沒想出來倔喂，能想到解法但時間復(fù)雜度壓不下去×玖常看的大佬的解答https://www.acwing.com/solution/content/5271/。這題說前綴里面去掉一個元素刻恭，其余元素出現(xiàn)的頻數(shù)全部相同晚顷，那么可以分成以下幾種情況：

• 1, 1, 1, ..., 1, 1
• 1, k, k, ..., k, k
• k, k, ..., k, k + 1
  由此發(fā)現(xiàn)要記錄每個數(shù)字出現(xiàn)的次數(shù)count，并且還要記錄每個“每個數(shù)字出現(xiàn)的次數(shù)”出現(xiàn)的次數(shù)freq浸卦，也就是說每種count的頻數(shù)是多少。我們還要記錄最大的freq的值就是頻數(shù)是多少案糙。那么根據(jù)上述分析的結(jié)論限嫌，寫一個if里面放三種可能性即可。這個題我感覺主要還是靠分析題目特點...感覺LeetCode里有好多不大好做的題都得找那個題的特有的規(guī)律和性質(zhì)时捌。雖然說這種東西也不是很好歸納怒医，但我打算找個機(jī)會把這種找特有性質(zhì)的題目一起復(fù)習(xí)一下。
  代碼：

class Solution {
    public int maxEqualFreq(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[100010];
        int[] freq = new int[100010];
        int maxFreq = 0, res = 0;
        
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (cnt[num] > 0) {
                freq[cnt[num]]--;
            }
            
            cnt[num]++;
            freq[cnt[num]]++;
            
            maxFreq = Math.max(maxFreq, cnt[num]);
            
            if (maxFreq == 1 || maxFreq * freq[maxFreq] + 1 == i + 1 || (maxFreq - 1) * (freq[maxFreq - 1] + 1) + 1 == i + 1) {
                res = i + 1;
            }
        }
        
        return res;
    }
}

LeetCode 1201

鏈接：https://leetcode.com/problems/ugly-number-iii/

方法：二分答案+數(shù)學(xué)（gcd+lcm）

時間復(fù)雜度：O(logm * logm), m代表數(shù)據(jù)范圍
想法：看一眼發(fā)現(xiàn)數(shù)據(jù)規(guī)模太大了奢讨，>=線性時間復(fù)雜度的統(tǒng)統(tǒng)沒戲稚叹。于是用數(shù)學(xué)方法做。所以說數(shù)學(xué)還是要學(xué)好，最起碼常見的問題什么gcd扒袖，lcm蛤奥，篩數(shù)法啊什么玩意的要會寫。那么選用二分法僚稿，每次分出來一個數(shù)mid，然后算小于等于mid的數(shù)里面蟀伸，丑數(shù)的個數(shù)是不是小于n個蚀同。怎么計算小于等于一個數(shù)的條件下，丑數(shù)的個數(shù)有多少個呢啊掏？我們會發(fā)現(xiàn)所謂丑數(shù)啊蠢络，就是a, b, c各自的倍數(shù)。一個直觀想法是(num / a) + (num / b) + (num / c)迟蜜。但我們會發(fā)現(xiàn)這里面會算重刹孔，因為比方說a和b的公倍數(shù)，在第一項里面加了一次娜睛，在第二項里面又加了一次髓霞，所以應(yīng)該刪掉這樣的元素一次，所以是減去(num / lcm(a, b))畦戒，當(dāng)然對b和c方库，a和c同理。那對于a, b, c共同的公倍數(shù)呢障斋？它們會在(num / a) + (num / b) + (num / c)里面加了三次纵潦，然后后面減，又給減了三次垃环，但實際上應(yīng)該對它們計一次數(shù)邀层。所以最后加上lcm(a, b, c)。這里用結(jié)論lcm(a,b,c) = lcm(a,lcm(b,c))遂庄。
代碼：

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        int low = 1, high = Integer.MAX_VALUE;
        
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            
            if (count(a, b, c, mid) < n) {
                low = mid;
            }
            else {
                high = mid;
            }
        }
        
        if (count(a, b, c, low) >= n) {
            return low;
        }
        
        return high;
    }
    
    private long gcd(long a, long b) {
        if (a == 0)
            return b;

        return gcd(b % a, a);
    }

    private long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }

    private int count(long a, long b, long c, long num) {
        return (int) ((num / a) + (num / b) + (num / c)
                - (num / lcm(a, b))
                - (num / lcm(b, c))
                - (num / lcm(a, c))
                + (num / lcm(a, lcm(b, c))));
    }
}