954.二倍数对数组

链接：954.二倍数对数组
难度：Medium
标签：贪心、数组、哈希表、排序
简介：给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 _ arr[2 _ i]” 时，返回 true；否则，返回 false。

题解 1 - cpp

• 编辑时间：2022-04-01
• 执行用时：100ms
• 内存消耗：56.9MB
• 编程语言：cpp
• 解法介绍：排序后检查。

class Solution {
   public:
    bool canReorderDoubled(vector<int> &arr) {
        deque<int> q1, q2;
        unordered_map<int, int> m;
        sort(arr.begin(), arr.end());
        for (auto &num : arr) {
            m[num]++;
            if (num >= 0 && (q1.empty() || q1.back() != num))
                q1.push_back(num);
            else if (num < 0 && (q2.empty() || q2.front() != num))
                q2.push_front(num);
        }
        return check(m, q1) && check(m, q2);
    }
    bool check(unordered_map<int, int> &m, deque<int> q) {
        while (q.size()) {
            int num = q.front();
            q.pop_front();
            if (m[num] == 0) continue;
            if (m[num * 2] < m[num]) return false;
            m[num * 2] -= m[num];
        }
        return true;
    }
};