【数组】最大相等频率

题目描述

给你一个正整数数组nums，请你帮忙从该数组中找出能满足下面要求的最长前缀，并返回该前缀的长度：

从前缀中恰好删除一个元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是0次）。

示例1：

输入：nums=[2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为7的子数组[2,2,1,1,5,3,3]，如果我们从中删去nums[4]=5，就可以得到[2,2,1,1,3,3]，里面每个数字都出现了两次。

解题思路

这道题就是找到一个从0到x到数组，这个数组满足：删除一个元素后其他元素个数相等。

针对：nums=[2,2,1,1,5,3,3,5]，思路如下：

• 统计每个元素的出现次数，2->2次、1->2次、5->2次、3->2次；
• 从右到左开始遍历数组
  • 不删除元素，2->2次、1->2次、5->2次、3->2次；不满足条件。
  • 删除最后一个元素5，2->2次、1->2次、5->1次、3->2次；由于 元素5 只出现一次，所以再把出现一次的5删除后得到：2->2次、1->2次、3->2次；所以满足条件返回结果[2,2,1,1,5,3,3]的长度：7.

这道题最复杂的是考虑所有可能的情况：

1. 所有元素出现频次都是1，那么一定满足条件；
2. 如果只有一个元素出现频次是1，其他频次都相等；那么删除出现频次是1的元素后，其他频次都相等，这个满足条件；
3. 如果只有一个元素出现频次最大该频次是n，其他元素频次相等都是为m；如果m+1==n，那么满足条件。

代码实现

 
import java.util.*;
 
class Solution {
    public int maxEqualFreq(int[] nums) {
        Map map = new HashMap<>();
 
        for (int i = 0; i < nums.length; i++) {
            int value = map.getOrDefault(nums[i], 0);
            map.put(nums[i], ++value);
        }
 
        // 如果只有一个数字直接返回
        if (map.size() == 1) {
            return nums.length;
        }
 
        if (check(null, map)) {
            return nums.length;
        }
 
        for (int i = nums.length; i > 0; i--) {
            if (check(nums[i - 1], map)) {
                return i - 1;
            }
        }
        return 1;
    }
 
    private boolean check(Integer num, Map map) {
 
        if (num != null) {
            int v = map.get(num);
            --v;
            if (v > 0) {
                map.put(num, v);
            } else {
                map.remove(num);
            }
        }
 
 
        List list = new ArrayList<>();
        Set set = new HashSet<>();
        for (int value : map.values()) {
            if (!set.contains(value)) {
                set.add(value);
            }
            list.add(value);
        }
        Collections.sort(list);
 
        if (set.size() == 1 && list.get(0) == 1) {
            return true;
        } else if (set.size() == 2) {
            int minCount = 0;
            int maxCount = 0;
 
            for (int value : list) {
                if (value == list.get(0)) {
                    minCount++;
                } else {
                    maxCount++;
                }
            }
            return minCount == 1 && list.get(0) == 1 || maxCount == 1 && list.get(0) + 1 == list.get(list.size() - 1);
        } else {
            return false;
        }
    }
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxEqualFreq(new int[]{2, 2, 1, 1, 5, 3, 3, 5}));
        System.out.println(solution.maxEqualFreq(new int[]{2, 1, 1, 1, 1, 3, 1, 1}));
        System.out.println(solution.maxEqualFreq(new int[]{2, 1, 3, 1, 1, 3, 1, 2}));
        System.out.println(solution.maxEqualFreq(new int[]{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5}));
        System.out.println(solution.maxEqualFreq(new int[]{1, 1, 1, 2, 2, 2, 3, 3, 3}));
        System.out.println(solution.maxEqualFreq(new int[]{1, 1, 1, 2, 2, 2}));
    }
}

这里对上面的代码进行一次优化，不使用MAP换用数组，并且最大值和最小值也不用SORT，代码改造后效果：

import java.util.*;
 
class Solution {
    //1 <= nums[i] <= 10 5
    public int maxEqualFreq(int[] nums) {
 
        int max = 0;
        for (int num : nums) {
            max = Math.max(num, max);
        }
 
        int[] map = new int[max + 1];
 
        for (int i = 0; i < nums.length; i++) {
            map[(nums[i])]++;
        }
 
        int count = 0;
        for (int v : map) {
            if (v != 0) {
                count++;
            }
        }
        if (count == 1) {
            return nums.length;
        }
 
        if (check(null, map)) {
            return nums.length;
        }
 
        for (int i = nums.length; i > 0; i--) {
            if (check(nums[i - 1], map)) {
                return i - 1;
            }
        }
        return 1;
    }
 
    private boolean check(Integer num, int[] map) {
 
        if (num != null) {
            map[(num)]--;
        }
 
 
        Set set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int minCount = 0;
        int max = Integer.MIN_VALUE;
        int maxCount = 0;
 
        for (int value : map) {
            if (value == 0) {
                continue;
            }
            if (!set.contains(value)) {
                set.add(value);
            }
 
            if (min > value) {
                min = value;
                minCount = 0;
            }
            if (min == value) {
                minCount++;
            }
 
            if (max < value) {
                max = value;
                maxCount = 0;
            }
            if (max == value) {
                maxCount++;
            }
        }
 
        if (set.size() == 1 && min == 1) {
            return true;
        } else if (set.size() == 2) {
            return minCount == 1 && min == 1 || maxCount == 1 && min + 1 == max;
        } else {
            return false;
        }
    }
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxEqualFreq(new int[]{100000, 100000}));
        System.out.println(solution.maxEqualFreq(new int[]{2, 2, 1, 1, 5, 3, 3, 5}));
        System.out.println(solution.maxEqualFreq(new int[]{2, 1, 1, 1, 1, 3, 1, 1}));
        System.out.println(solution.maxEqualFreq(new int[]{2, 1, 3, 1, 1, 3, 1, 2}));
        System.out.println(solution.maxEqualFreq(new int[]{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5}));
        System.out.println(solution.maxEqualFreq(new int[]{1, 1, 1, 2, 2, 2, 3, 3, 3}));
        System.out.println(solution.maxEqualFreq(new int[]{1, 1, 1, 2, 2, 2}));
    }
}

总结

这道题我主要时间都在做验证，很多case都要覆盖，整个严谨性还需要提高；欢迎有更快、更简洁的思路回复。