954. Array of Doubled Pairs

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 同步地址:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation