一定要早日上岸鸭 · July 19, 2021 0

1838. 最高频元素的频数

1838. 最高频元素的频数

法一:枚举和哈希:

class Solution { public int maxFrequency(int[] nums, int k) { int N = nums.length; int ans = 1; Map<Integer,Integer> hm = new HashMap<Integer, Integer>(); List<Integer> list = new ArrayList<Integer> (); for(int i=0; i<N; i++) hm.put(nums[i], hm.getOrDefault(nums[i],0)+1); list.addAll(hm.keySet()); Collections.sort(list); for(int i=0; i<list.size(); i++){ int right = list.get(i), cnt = hm.get(right); int p = k; for(int j=i-1; j>=0; j--){ int left=list.get(j), diff = right - left; if(p>=diff){ int add = p/diff; // 这一步是为了要么按照key对应的值来进行计算直到和当前x一样,要么按照能够加的最大数量来进行计算直到和当前x一样 // 就是说他与可能本可以加多次但是由于只有1个数导致只能加1次 int min = Math.min(hm.get(left), add); // 计算由于操作的次数而损失的k值 p = p - min*diff; cnt += min; } else{ break; } } ans = Math.max(ans, cnt); } return ans; } }

法2:二分查找右端点+前缀和+滑动窗口

class Solution { public int maxFrequency(int[] nums, int k) { // 构造前缀和数列: int N = nums.length; int[] sum = new int[N+1]; Arrays.sort(nums); for(int i=1; i<=N; i++) sum[i] = sum[i-1]+nums[i-1]; int l = 0, r = N; while(l<r){ int mid = l+r+1>>1; if(check(nums,sum, mid, k)) l = mid; else r = mid-1; } return r; } public boolean check(int[] nums, int[] sum, int len, int k){ int l = 0; while(l+len-1<nums.length){ int r = l+len-1; int cur = sum[r+1]-sum[l]; int t = nums[r]*(r-l+1); if(t-cur<=k) return true; l++; } return false; } }