Leetcode 1838. Frequency of the Most Frequent Element

[Woodyiiiiiii]

Leetcode 1838. Frequency of the Most Frequent Element

1838. Frequency of the Most Frequent Element

这道每日一题我竟然没做出来。

我的第一想法是贪心，对每个数在k范围下求其能达到的最大frequency，这就需要对比他小的数进行选择，但如果一个个选的话，就有叠加的关系，而且比较复杂，不容易算。我尝试用TreeMap记录，然后遍历，但发现没有思路。

其实破题关键在于用和来计算整体。比如要使某个数num达到频率a，那就要其一段subarray的数值之和加上k大于等于num * a。

Sliding Windows + Sort

既然要用subarray，那就可以用sliding window了。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int l = 0, r = 0;
        long sum = 0;
        int ans = 0;
        while (r < n) {
            sum += nums[r];
            while (sum + k <  (long)(nums[r]) * (r - l + 1)) {
                sum -= nums[l++];
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
}

Binary Search + Sort + Prefix Sum

既然涉及到和，那也就可以用前缀和+二分的方式。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] prefixSum = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            prefixSum[i] = sum;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l = 0, r = i + 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                long sum1 = prefixSum[i] - (mid == 0 ? 0 : prefixSum[mid - 1]);
                if (sum1 + k >= (long) nums[i] * (i - mid + 1)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans = Math.max(ans, i - l + 1);
        }
        return ans;
    }
}