# 2007. Find Original Array From Doubled Array
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/find-original-array-from-doubled-array/
## 思路 $O(N+klogk)$ $O(k)$
和[0954. Array of Doubled Pairs](https://hackmd.io/mn_aZ5V1TeiFygLVc5Gt2Q)差不多
$k$是unique number的数量
首先将数字都存到map里统计frequency
然后排序
对于一个数$a$，如果发现$2a$出现的频率比$a$小，则直接return空array
否则就把 $a$出现频率 个$a$放进答案里面
这里要注意的是如果$a$是0，只能放出现频率一半的$a$，所以每次放一个$a$之后，就把$2a$的频率-1
## Code

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if(n%2==1) return new int[0];
        Map<Integer, Integer> map = new TreeMap<>();
        for(int num:changed){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int[] ans = new int[n/2];
        int idx = 0;
        for(int key:map.keySet()){
            if(map.get(key)>map.getOrDefault(key+key, 0)){
                return new int[0];
            }
            for(int i=0; i<map.get(key); i++){
                ans[idx++] = key;
                map.put(2*key, map.get(2*key)-1);
            }
        }
        return ans;
    }
}