题目描述

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

样例

输入：[3,1,3,6]
输出：false

输入：[2,1,2,6]
输出：false

输入：[4,-2,2,-4]
输出：true
解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

输入：[1,2,4,16,8,4]
输出：false

注意

• 0 <= A.length <= 30000
• A.length 为偶数
• -100000 <= A[i] <= 100000

算法

(贪心构造) $O(n \log n)$

1. 将数组分为负数和非负数两部分，负数部分从大到小排序，非负数部分从小到大排序。
2. 排序后，对于每一部分，维护两个指针 $i$ 和 $j$，初始为 0。以非负数部分为例，对于每个未被标记的 pos[i]，都从上一次 $j$ 开始寻找，如果 pos[i] * 2 == pos[j]，则匹配成功， i 向后移动，同时标记 j 已经使用过了。如果没有找到这样的 $j$，则宣告失败。负数部分同理。

时间复杂度

• 排序后，每个数字最多被遍历两次，故总时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        int n = A.size();
        vector<int> pos, neg;
        vector<bool> vis_p, vis_n;
        for (int i = 0; i < n; i++) {
            if (A[i] >= 0) {
                pos.push_back(A[i]);
                vis_p.push_back(false);
            }
            else {
                neg.push_back(A[i]);
                vis_n.push_back(false);
            }
        }

        sort(pos.begin(), pos.end());
        sort(neg.begin(), neg.end());
        reverse(neg.begin(), neg.end());

        if (pos.size() % 2 == 1)
            return false;

        bool flag;
        for (int i = 0, j = 0; i < pos.size(); i++) {
            if (vis_p[i])
                continue;
            flag = false;
            while (j < pos.size()) {
                j++;
                if (pos[j] == pos[i] * 2) {
                    vis_p[j] = true;
                    flag = true;
                    break;
                }
            }
            if (!flag)
                return false;
        }

        for (int i = 0, j = 0; i < neg.size(); i++) {
            if (vis_n[i])
                continue;
            flag = false;
            while (j < neg.size()) {
                j++;
                if (neg[j] == neg[i] * 2) {
                    vis_n[j] = true;
                    flag = true;
                    break;
                }
            }
            if (!flag)
                return false;
        }

        return true;
    }
};