[LeetCode] 954. Array of Doubled Pairs

[grandyang]

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: [3,1,3,6]
Output: false

Example 2:

Input: [2,1,2,6]
Output: false

Example 3:

Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: [1,2,4,16,8,4]
Output: false

Note:

1. 0 <= A.length <= 30000
2. A.length is even
3. -100000 <= A[i] <= 100000

这道题说是给了一个偶数长度的数组，问能不能重新排序，使得从开头起，每两个组成一个对，其中后面的数字是前面的数字的两倍。题目中的坐标啥的不用管，本质就是将所有的数字两两分组，一个数是另一个数字的两倍就行了。博主最开始的方法是用一个 HashSet，对于每个数字，查找是其2倍的数字和是其二分之一的数字（必须整除），若在 HashSet 中存在，则将其移除，否则将遍历数字加入 HashSet，最后看 HashSet 是否为空。这种方法不适用于有重复数字的情况，所以需要换成 HashMap 来做，然后建立每个数字与其出现次数之间的映射。为了简便搜索的过程，可以给数字排序，这样就可以从最小的数字开始处理，只要查找其2倍的数字即可。但是当数组中存在负数的时候，直接排序还是会出问题，比如 -8 会排在 -4 前面，但其实是需要先处理 -4 的，因为 -4 x 2 = -8。所以需要自定义排序的规则，按照数字的绝对值大小排序，这样 -4 就可以排在 -8 前面。排好序了之后就可以从开头处理数字了，对于每个数字 key，假如其出现次数大于 key 的2倍的数字出现个数，则说明一定多余的 key 无法匹配，直接返回 false。否则 key 的2倍数字的映射值减去 key 的映射值，并接续遍历即可，参见代码如下：

解法一：

class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        unordered_map<int, int> m;
        for (int num : A) ++m[num];
        vector<int> keys;
        for (auto &a : m) keys.push_back(a.first);
        sort(keys.begin(), keys.end(), [](int i, int j) {return abs(i) < abs(j);});
        for (int key : keys) {
            if (m[key] > m[2 * key]) return false;
            m[2 * key] -= m[key];
        }
        return true;
    }
};

我们也可以使用 TreeMap 来建立映射，利用其自动排序的特性。但是这里还是存在上面提到的负数的问题，则需要特殊的处理一下。从最小的数字开始处理，由于可能先处理 -8，而不是 -4，所以在找目标数字的时候需要判断这个数字的正负，若是负数，则除以2，若是正数，则乘以2。然后在判断假如当前数字是负数，且还是奇数，则直接返回 false，因为没有比该数还小的数字，所以不能乘以2，又因为其是奇数，不能除以2，所以注孤生。还有就是判断若当前数字的映射值大于目标数字的映射值，也直接返回 false，这个在上面的解法中解释过了。之后目标的映射值减去当前数字的映射值，当遍历结束之后返回 true，参见代码如下：

解法二：

class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        map<int, int> m;
        for (int num : A) ++m[num];
        for (auto &a : m) {
            if (a.second == 0) continue;
            int want = a.first < 0 ? a.first / 2 : a.first * 2;
            if ((a.first < 0 && a.first % 2 != 0) || a.second > m[want]) return false;
            m[want] -= a.second;
        }
        return true;
    }
};

Github 同步地址:

#954

参考资料：

https://leetcode.com/problems/array-of-doubled-pairs/

https://leetcode.com/problems/array-of-doubled-pairs/discuss/209564/Java-Heap-Concise

https://leetcode.com/problems/array-of-doubled-pairs/discuss/203183/JavaC%2B%2BPython-Match-from-the-Smallest-or-Biggest-100

LeetCode All in One 题目讲解汇总(持续更新中...)