LeetCode - 954. 二倍数对数组

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：计数，先特判0（0只能与自己组对）。
剩下的从绝对值小的入手开始组对，然后为2*x减去组对成功的个数。
如果全部组对成功则返回true。

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int, int> cnt;
        for (int x: arr) {
            cnt[x]++;
        }
        if (cnt[0] % 2) return false;
        vector<int> vals; vals.reserve(cnt.size());
        for (auto &[x, _] : cnt) {
            vals.push_back(x);
        }
        sort(vals.begin(), vals.end(), [](int a, int b){ return abs(a)<abs(b); });
        for (int x : vals) {
            if (cnt[2*x] < cnt[x]) {
                return false;
            }
            cnt[2*x] -= cnt[x];
        }
        return true;
    }
};

总结：有一系列x与2*x的约束。看似错综复杂，实际可从两端边界入手（此题绝对值最小或绝对值最大的。
绝对值最小的不可能再有更小的来干扰判断，只可能跟它的两倍相关。

Donate