LeetCode 1224

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

方法：

时间复杂度：O(n)
想法：我当时没想出来，能想到解法但时间复杂度压不下去。看的大佬的解答https://www.acwing.com/solution/content/5271/。这题说前缀里面去掉一个元素，其余元素出现的频数全部相同，那么可以分成以下几种情况：

• 1, 1, 1, ..., 1, 1
• 1, k, k, ..., k, k
• k, k, ..., k, k + 1
  由此发现要记录每个数字出现的次数count，并且还要记录每个“每个数字出现的次数”出现的次数freq，也就是说每种count的频数是多少。我们还要记录最大的freq的值就是频数是多少。那么根据上述分析的结论，写一个if里面放三种可能性即可。这个题我感觉主要还是靠分析题目特点...感觉LeetCode里有好多不大好做的题都得找那个题的特有的规律和性质。虽然说这种东西也不是很好归纳，但我打算找个机会把这种找特有性质的题目一起复习一下。
  代码：

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/

方法：二分答案+数学（gcd+lcm）

时间复杂度：O(logm * logm), m代表数据范围
想法：看一眼发现数据规模太大了，>=线性时间复杂度的统统没戏。于是用数学方法做。所以说数学还是要学好，最起码常见的问题什么gcd，lcm，筛数法啊什么玩意的要会写。那么选用二分法，每次分出来一个数mid，然后算小于等于mid的数里面，丑数的个数是不是小于n个。怎么计算小于等于一个数的条件下，丑数的个数有多少个呢？我们会发现所谓丑数啊，就是a, b, c各自的倍数。一个直观想法是(num / a) + (num / b) + (num / c)。但我们会发现这里面会算重，因为比方说a和b的公倍数，在第一项里面加了一次，在第二项里面又加了一次，所以应该删掉这样的元素一次，所以是减去(num / lcm(a, b))，当然对b和c，a和c同理。那对于a, b, c共同的公倍数呢？它们会在(num / a) + (num / b) + (num / c)里面加了三次，然后后面减，又给减了三次，但实际上应该对它们计一次数。所以最后加上lcm(a, b, c)。这里用结论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))));
    }
}