数组大小减半

数组大小减半(medium)

做题过程

我用了哈希表和排序完成，实际上也就是贪心。

算法概述

本题要求为给出一个带有多个重复元素的数组，返回使原数组长度至少减半的最少删除的重复元素的数量。使用 哈希表+排序 。

时间复杂度为O(nlongn)
空间复杂度为O(n)

JAVA

class Solution {
    public int minSetSize(int[] arr) {
        List<Integer> oc=new ArrayList<>();
        Map<Integer,Integer> map=new HashMap<>();
        map.put(arr[0],1);
        for(int a:arr){
            map.put(a,map.getOrDefault(a,0)+1);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            Integer value=entry.getValue();
            oc.add(value);
        }
        Collections.sort(oc,Collections.reverseOrder());
        int sum=0;
        int ans=0;
        for(int i=0;i!=oc.size();++i){
            sum+=oc.get(i);
            ans+=1;
            if(sum>arr.length/2) break;
        }
        return ans;
    }
}

重要实例及方法(JAVA)

Collections.reverseOrder()：反向比较器
List<Integer> occ = new ArrayList<>(freq.values());：可以直接通过构造器建列表，不需要Map.entrySet()

总结

对实例方法的使用还有待提升。