给定一个无序整数流，保持排序，但删除数组中只出现一次的元素

Question

我的解决方案：

public class removeUniqueElements {
    public static Integer[] removeUnique(int[] arr){
        Map<Integer,Integer> output = new HashMap<Integer,Integer>();
        List<Integer> result = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            if(output.containsKey(arr[i])){
                int count = output.get(arr[i]);
                count = count+1;
                output.put(arr[i],count);
            }
            else
            {
                output.put(arr[i],1);
            }
        }
        for(int i=0;i<arr.length;i++){
            if(output.get(arr[i])!=1){
                result.add(arr[i]);
            }
        }
        return result.toArray(new Integer[result.size()]);
    }
    public static void main(String[] args){
        int[] array = {1,2,3,4,2,3,4};
        Integer[] result = removeUnique(array);
        System.out.println(Arrays.toString(result));
    }
}

时间复杂度 ： O（n）空间复杂度 ： O（n）

有没有其他方法可以降低空间复杂性？请帮忙。

Answer 1

为了获得更好的性能，请使用 Map<Integer, AtomicInteger> ，这样您就可以简单地更新映射的计数器，而不是在每次递增计数器时都装箱一个新值。这也将减少产生的垃圾量，这可以被认为是内存占用的减少，即使从技术上讲并非如此。

为了减少内存占用，请勿使用 List<Integer> 或 Integer[] 。将所有值装箱到 Integer 中是大量的对象开销，首先创建一个列表，然后创建最后一个数组，意味着消耗 2 倍的引用数量。

相反，构建

地图后，计算要删除的值的数量，然后直接创建结果数组并填充它。没有拳击，也没有空间浪费在List上。

我将留给您调整这些改进的代码。

Answer 2

你可以

使用 Java8：

Arrays.stream(arr).collect(Collectors.groupingBy(Function.identity()).
       entrySet().stream().filter(e -> e.getValue().size() != 1).
       map(e -> e.getValue()).toArray(int[]::new);