2856. 删除数对后的最小数组长度 (opens new window)

1.优先级队列

解题思路：考虑用例3,3,3,4,4,4,4,5,5,5。可以发现要想保证剩余数组最小，对所选择作为删除数对的数的频次有一定的要求，题目已经保证数组有序，因此频次越多的数需要优先和其它的数进行消除。具体的，每次需要选择频次最多的两个数作为删除的数对。

维护一个小顶堆，队首元素为出现频次最大的元素。时间复杂度为O(n)

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        Map<Integer,int[]> map=new HashMap<>();
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o2[1]-o1[1];
            }
        });
        int res=nums.size();
        for(int i=0;i<nums.size();i++){
            if(!map.containsKey(nums.get(i))){
                int[] tmp=new int[]{nums.get(i),1};
                map.put(nums.get(i),tmp);
            }
            else{
                map.get(nums.get(i))[1]++;
            }
        }
        for (int[] value : map.values()) {
            queue.offer(value);
        }
        while(queue.size()>1){
            int[] tmp1=queue.poll();
            int[] tmp2=queue.poll();
            tmp1[1]--;
            tmp2[1]--;
            if(tmp1[1]>0)queue.offer(tmp1);
            if(tmp2[1]>0)queue.offer(tmp2);
            res-=2;
        }
        return res;
    }
}

2.二分思路

假设某个数达到最大出现频次cnt，分类讨论cnt*2与n的大小关系。

题目转换为求出cnt，在有序数组中可以使用二分的方法找到最大频次的数的首尾索引坐标。