[LeetCode] 954. Array of Doubled Pairs 两倍数对儿数组

标签：ems   issue   oss   als   code   log   https   example   NPU   

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 .

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
2. A.length?is even
3. -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& A) {
        unordered_map m;
        for (int num : A) ++m[num];
        vector keys;
        for (auto &a : m) keys.push_back(a.first);
        sort(keys.begin(), keys.end(), [](int i, int j) {return abs(i)  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& A) {
        map m;
        for (int num : A) ++m[num];
        for (auto &a : m) {
            if (a.second == 0) continue;
            int want = a.first  m[want]) return false;
            m[want] -= a.second;
        }
        return true;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中...)

[LeetCode] 954. Array of Doubled Pairs 两倍数对儿数组

标签：ems   issue   oss   als   code   log   https   example   NPU   

原文地址：https://www.cnblogs.com/grandyang/p/13380161.html