[数据结构与算法]leetcode:954. 二倍数对数组

954. 二倍数对数组

来源：力扣（LeetCode）

链接: https://leetcode-cn.com/problems/array-of-doubled-pairs/

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

$0<=arr.length<=3?10^4$
arr.length 是偶数
$?10^5<=arr[i]<=10^5$

解法

模拟法：假设$arr=[2,4,4,8,8,16]$

• 对于重组后，每个下标的元素有对应的$arr[2?i+1]=2?arr[2?i]$
• [2, 4]匹配完成后，4的个数减少1次，4的个数从2个变成1个，2的个数变为0个；
• [4, 8]匹配完成后，8的个数减少1次，8的个数从2个变成1个，4的个数变为0个；
• [8, 16]匹配完成后，16的个数减少1次，16的个数从1个变为0个，此时8的个数变为0个；

以此类推，大小数字的个数关系需要满足：

$$num\_map[num]<=num\_map[2?num]$$

由于大的数还会被用于作为后续数字的 num, 每次匹配完成大的数据需要减去小的数据个数:

$$num\_map[2?num]?=num\_map[num]$$

边界说明：

• 对于出现0的特殊情况，arr.length 是偶数 题目提示已经给出，如果只有一个0，必定存在另外一个数不能配对，题目必定不满足， 不需要特殊考虑
• 对于 num 为负数，这里和数值正负就没关系，只涉及倍数关系，只与 num 的绝对值大小有关，不需要去考虑
• python Counter 数据结构自带默认值0，key 不存在就返回 default = 0 不需要去考虑

栈遍历： 先对列表元素进行排序，然后使用栈进行保存遍历元素，入栈前先与头元素进行比较，注意正负的问题，如果满足二倍的关系，将头元素pop出来，如果不满足，就入栈。最终判断栈中元素是否为空，为空的话则为True，否则为False；

代码实现

模拟法：

• python实现

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        num_map = collections.Counter(arr)
        for num in sorted(num_map, key=abs):
            if num_map[num] > num_map[2*num]:
                return False
            num_map[2*num] -= num_map[num]
        return True

• c++实现

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)  // 遍历map的一种方式，可以写成auto [k,v]:map ，k表示键，v表示值
        {
            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]) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};

栈遍历：

• python实现

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        arr.sort()
        stack = []
        for num in arr:
            if len(stack) == 0:
                stack.append(num)
            elif num == 2 * stack[0] or stack[0] == 2* num:  # 正负元素比较 [2, 4] [-4, -2]
                stack.pop(0)
            else:
                stack.append(num)
        return len(stack) == 0

• c++实现

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        queue<int> q;
        for(int e: arr)
        {
            if(q.empty())
            {
                q.push(e);
            }
            else if(e*2 == q.front() || q.front() * 2 == e)  // 正负元素比较 [2, 4] [-4, -2]
            {
                q.pop();
            }
            else{
                q.push(e);
            }
        }
        return q.empty();
    }
};

复杂度分析

• 时间复杂度： $O(nlogn)$ 排序耗时
• 空间复杂度： $O(n)$ 哈希表, 栈