leetcode:954. 二倍数对数组

954. 二倍数对数组

来源：力扣（LeetCode）

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

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 < = i < l e n ( a r r ) / 2 0 <= i < len(arr) / 2 0<=i<len(arr)/2，都有 a r r [ 2 ∗ i + 1 ] = 2 ∗ a r r [ 2 ∗ i ] arr[2 * i + 1] = 2 * arr[2 * i] 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 < = a r r . l e n g t h < = 3 ∗ 1 0 4 0 <= arr.length <= 3 * 10^4 0<=arr.length<=3∗104
arr.length 是偶数
− 1 0 5 < = a r r [ i ] < = 1 0 5 -10^5 <= arr[i] <= 10^5 −105<=arr[i]<=105

解法

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

• 对于重组后，每个下标的元素有对应的 a r r [ 2 ∗ i + 1 ] = 2 ∗ a r r [ 2 ∗ i ] arr[2 * i + 1] = 2 * arr[2 * i] 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个；

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

n u m _ m a p [ n u m ] < = n u m _ m a p [ 2 ∗ n u m ] num\_map[num] <= num\_map[2*num] num_map[num]<=num_map[2∗num]

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

n u m _ m a p [ 2 ∗ n u m ] − = n u m _ m a p [ n u m ] num\_map[2* num] -= num\_map[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& arr) {
        sort(arr.begin(), arr.end());
        queue 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 ( n l o g n ) O(nlogn) O(nlogn) 排序耗时
• 空间复杂度： O ( n ) O(n) O(n) 哈希表, 栈