# 0954. Array of Doubled Pairs
###### tags: `Leetcode` `Medium` `Google`
Link: https://leetcode.com/problems/array-of-doubled-pairs/
## 思路 $O(N+klogk)$ $O(k)$
和[2007. Find Original Array From Doubled Array](https://hackmd.io/Y-esg71RQ5iNb5Knm5K0pA)差不多
$k$是unique number的数量
首先将数字都存到map里统计frequency
然后排序
这里要注意对于一个数$a$，如果$a<0$，下一个数是$a/2$，如果$a>0$，下一个数是$a*2$，记$a$出现的频率为$count$, 下一个数（$a/2$或$a*2$）出现的频率为$count2$
- 如果$count=0$，什么都不做
- 如果$count>count2$，则return false，因为多余的$a$一定组不成pair
- 其他情况说明$a$可以组成pair，那么就把$a$和$a$的下一个数在map里对应的值减掉$count$

之所以不用像[2007. Find Original Array From Doubled Array](https://hackmd.io/Y-esg71RQ5iNb5Knm5K0pA)那样特别考虑0，是因为这里不需要计算出现了几次0，只要知道0出现了偶数次就可以了，因为arr的长度已经说了是偶数，所以只要其他的数都合法（没有return false），0出现的次数也一定是偶数，当$a=0$的时候，$cnt$里面0对应的值会被减成负数，但是没有关系
## Code

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int num:arr){
            cnt.put(num, cnt.getOrDefault(num, 0)+1);
        }
        List<Integer> keys = new ArrayList<>(cnt.keySet());
        Collections.sort(keys);
        for(int num:keys){
            int count = cnt.get(num);
            if(count==0) continue;
            else if(num<0 && num%2!=0) return false;
            int next = num<0?num/2:num*2;
            if(cnt.getOrDefault(next,0)<count) return false;
            cnt.put(num, 0);
            cnt.put(next, cnt.get(next)-count);
        }
        return true;
    }
}