Google FooBar挑战：数组移除超N次元素Java代码bug排查

题目要求 #

编写名为solution(data, n)的函数，接收长度小于100的整数列表与数值n，返回将原列表中出现次数超过n次的数字全部移除后的列表。返回的列表需保留原列表的顺序，避免打乱预先规划的轮班顺序！

示例：若data为[5, 10, 15, 10, 7]、n为1，solution(data, n)应返回[5, 15, 7]，因为10出现2次，需从列表中完全移除。

故障表现 #

提交的实现10个测试用例仅通过2个，其中公开测试用例输入{1, 2, 2, 3, 3, 3, 4, 5, 5}、n = 1提交后运行失败，但相同输入在本地IDE可正常运行。
原始实现代码如下：

public static int[] solution(int[] data, int n) {
    Map<Integer, Integer> map = new LinkedHashMap<>();
    
    if (data.length < 1) {
        return data;
    }
    
    if (n < 1) {
        return new int[0];
    }
    
    for (final int datum : data) {
        map.put(datum, map.getOrDefault(datum, 0) + 1);
    }
    
    List<Integer> t = map.entrySet()
        .stream()
        .filter(x -> x.getValue() == 1)
        .map(Map.Entry::getKey)
        .toList();
    
    int[] b = new int[t.size()];
    
    for (int i = 0; i < t.size(); i++) {
        b[i] = t.get(i);
    }
    
    return b;
}

代码存在的核心问题 #

• 过滤条件硬编码为判断出现次数等于1，完全没有使用传入的参数n。题目要求是移除出现次数超过n次的元素，即保留出现次数≤n的元素，当n≠1时逻辑完全错误。
• 结果生成逻辑错误：直接遍历频次统计的Map键集合构造结果，Map的键是去重的，这会导致原列表中出现次数合规的重复元素被全部丢弃，完全无法保留原列表的元素顺序和重复结构。比如输入[2,2,1]、n=2时，正确结果应该是[2,2,1]，现有代码只会返回[2,1]。
• 运行环境兼容性问题：代码中使用了Stream.toList()方法，该方法是Java 16版本新增的API，Google FooBar的Java运行环境为Java 8，不存在该方法，提交后会直接抛出方法不存在的错误，这也是本地高版本JDK运行正常，但提交判题失败的直接原因。

修正思路 #

1. 第一步遍历原数组统计每个数字的出现频次，这部分原有逻辑可保留。
2. 第二步重新遍历原数组，逐个检查当前元素的出现频次，如果频次≤n就加入结果列表，既可以正确按参数n过滤，也能完全保留原数组的顺序和合法的重复元素。
3. 最后将结果列表转为int数组返回即可，全程避免使用高版本Java API，保证兼容判题环境。

修正后的参考代码：

public static int[] solution(int[] data, int n) {
    if (data.length < 1) {
        return data;
    }
    
    if (n < 1) {
        return new int[0];
    }
    
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int datum : data) {
        countMap.put(datum, countMap.getOrDefault(datum, 0) + 1);
    }
    
    List<Integer> resultList = new ArrayList<>();
    for (int datum : data) {
        if (countMap.get(datum) <= n) {
            resultList.add(datum);
        }
    }
    
    int[] result = new int[resultList.size()];
    for (int i = 0; i < resultList.size(); i++) {
        result[i] = resultList.get(i);
    }
    return result;
}

内容的提问来源于stack exchange，提问作者newLearner