题目来源

力扣每日一题；题序：2007

我的题解

方法一 排序+哈希表

先对change数组升序排序，然后使用哈希表存储未能匹配消除（一个数是另一个数的两倍）的数及其出现次数，在过程中使用一个list存储结果；最后看哈希表是否还有key，若无则表示能匹配；否则表示不能匹配

时间复杂度：O(nlogn)。主要是排序的耗时
空间复杂度：O(n)

public int[] findOriginalArray(int[] changed) {
    int n=changed.length;
    if(n%2==1)
        return new int[0];
    Map<Integer,Integer> map=new HashMap<>();
    List<Integer> res=new ArrayList<>();
    Arrays.sort(changed);
    for(int i=0;i<n;i++){
        int num=changed[i];
        int bNum=num/2;
        if(num%2==0&&map.containsKey(bNum)&&map.get(bNum)!=0){
            map.put(bNum,map.get(bNum)-1);
            if(map.get(bNum)==0)
                map.remove(bNum);
            res.add(bNum);
        }else{
            map.put(num,map.getOrDefault(num,0)+1);
        }
    }
    if(map.size()!=0)
        return new int[0];
    int[] ans=new int[res.size()];
    for(int i=0;i<res.size();i++)
        ans[i]=res.get(i);
    return ans;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~