每日一题 二倍数对数组

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

954. 二倍数对数组

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

示例：

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

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

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

思路：

我们用哈希表记录每个数出现的次数，然后排序，计算当前数的 2 倍， 负数为除 2， 正数为乘 2。

如果存在这个数，并且这个数的哈希值不为0，则在哈希表中数量减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<float , int> mp;
        //记录每个数出现次数
        for(int a : arr){
            mp[a]++;
        }
        sort(arr.begin(), arr.end());
        for(int value : arr){
            //当前数已经匹配完则继续遍历下一个
            if(mp[value] == 0){
                continue;
            }
            float target;
            //计算当前数对2倍，负数除 2， 正数乘 2
            if(value >= 0){
                target = 2 * value;
            }else{
                target = value / 2.0;
            }

            //不存在 2 的倍数或者已经匹配完了，则返回false
            if(!mp.count(target) || mp[target] == 0){
                return false;
            }else{
                //对应数的数量减一
                mp[target]--;
                mp[value]--;
            }
        }
        return true;
    }
};