Medium

题目描述

给定一个长度为偶数的整数数组 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]。

提示：

  • 2 <= arr.length <= 3 * 10^4
  • arr.length 是偶数
  • -10^5 <= arr[i] <= 10^5

解题思路

解题思路

这道题的核心是要判断数组中的元素能否两两配对，形成 (x, 2x) 的形式。

方法分析：

  1. 哈希表计数法：统计每个数字的出现次数，然后按照绝对值从小到大的顺序进行配对。对于每个数字 x，尝试与 2x 配对。

  2. 排序贪心法：先对数组排序，然后依次处理每个元素，优先与其二倍值配对。

推荐解法：哈希表计数法

核心思想是：

  1. 使用哈希表统计每个数字的出现次数
  2. 按照数字绝对值从小到大的顺序处理（避免处理顺序问题）
  3. 对于每个数字 x，如果它还有剩余，就尝试与 2x 配对
  4. 特别处理 0 的情况：0 只能与 0 配对，所以 0 的个数必须是偶数

这种方法的优势是避免了复杂的排序逻辑，特别是在处理负数时更加直观。

时间复杂度：遍历数组统计次数 O(n)，处理配对 O(n)，总体 O(n) 空间复杂度：哈希表存储 O(n)

代码实现

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int x : arr) {
            count[x]++;
        }
        
        vector<int> keys;
        for (auto& p : count) {
            keys.push_back(p.first);
        }
        
        sort(keys.begin(), keys.end(), [](int a, int b) {
            return abs(a) < abs(b);
        });
        
        for (int x : keys) {
            if (count[x] == 0) continue;
            
            if (x == 0) {
                if (count[x] % 2 != 0) return false;
                count[x] = 0;
            } else {
                if (count[2 * x] < count[x]) return false;
                count[2 * x] -= count[x];
                count[x] = 0;
            }
        }
        
        return true;
    }
};

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        from collections import Counter
        
        count = Counter(arr)
        
        # 按绝对值排序
        for x in sorted(count, key=abs):
            if count[x] == 0:
                continue
            
            if x == 0:
                if count[x] % 2 != 0:
                    return False
                count[x] = 0
            else:
                if count[2 * x] < count[x]:
                    return False
                count[2 * x] -= count[x]
                count[x] = 0
        
        return True

public class Solution {
    public bool CanReorderDoubled(int[] arr) {
        var count = new Dictionary<int, int>();
        foreach (int x in arr) {
            count[x] = count.GetValueOrDefault(x, 0) + 1;
        }
        
        var keys = new List<int>(count.Keys);
        keys.Sort((a, b) => Math.Abs(a).CompareTo(Math.Abs(b)));
        
        foreach (int x in keys) {
            if (count[x] == 0) continue;
            
            if (x == 0) {
                if (count[x] % 2 != 0) return false;
                count[x] = 0;
            } else {
                if (!count.ContainsKey(2 * x) || count[2 * x] < count[x]) {
                    return false;
                }
                count[2 * x] -= count[x];
                count[x] = 0;
            }
        }
        
        return true;
    }
}

var canReorderDoubled = function(arr) {
    const count = new Map();
    
    for (const num of arr) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const keys = Array.from(count.keys()).sort((a, b) => Math.abs(a) - Math.abs(b));
    
    for (const num of keys) {
        if (count.get(num) > 0) {
            const double = num * 2;
            const numCount = count.get(num);
            const doubleCount = count.get(double) || 0;
            
            if (doubleCount < numCount) {
                return false;
            }
            
            count.set(double, doubleCount - numCount);
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，其中 n 为数组长度
空间复杂度O(n)哈希表存储所有元素的计数信息

相关题目