Leetcode 964.二倍数对数组_C

原题链接：Leetcode 954. Array of Doubled Pairs

Given an integer array of even length arr, return true if it is possible to reorder arr such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2, or false otherwise.

Example 1:

Input: arr = [3,1,3,6]
Output: false

Example 2:

Input: arr = [2,1,2,6]
Output: false

Example 3:

Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Constraints:

2 <= arr.length <= 3 * 10⁴
arr.length is even（偶数）.
-105 <= arr[i] <= 105

做法一：哈希表+排序思路：

题目问的是给一个整数数组，该数组能否分成n / 2个数对，其中每个数对都有一个数x和它的两倍2x组成。

首先用哈希表记录每个数出现的次数；
0只能和0进行组合，因此如果0的个数是奇数，可以提前返回false退出；
对于剩下的元素，按绝对值从小到大，去判断x的个数是否大于2x的个数，如果有就返回false退出；
否则就去掉2x对应的个数，直到所有元素均被判断过返回true

c++代码：

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        // 统计每个数出现的次数
        unordered_map<int, int> cnt;
        for(auto a:arr)
            cnt[a]++;
        
        // 特判 如果0有奇数个
        if(cnt[0] % 2)  return false;

        vector<int> val;
        // reserve()的作用是预留空间
        val.reserve(cnt.size());
        for(auto [x, _] : cnt) val.emplace_back(x);
        // 按绝对值从小到大排列
        sort(val.begin(), val.end(), [](int a, int b){ return abs(a) < abs(b); });

        for(auto v : val){
            if(cnt[v] > cnt[2 * v]) return false;
            else{
                cnt[2 * v] -= cnt[v];
            }
        }
        return true;
    }
};

python3代码：

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        cnt = Counter(arr)

        if cnt[0] % 2:
            return False
        
        for i in sorted(cnt, key=abs):
            if cnt[i] > cnt[2 * i]:
                return False
            else:
                cnt[2 * i] -= cnt[i]
        return True