LeetCode 954. 二倍数对数组

Categories:

题目描述
思路分析
1. 解法一：排序 + 贪心（推荐）
相似题目

题目描述

✅ 954. 二倍数对数组

思路分析

解法一：排序 + 贪心（推荐）

核心思路：

将数组按绝对值从小到大排序，保证每次遇到一个数时，其对应的”一半”或”二倍”一定已经或正在被处理

使用哈希表记录每个数字剩余的未配对数量

按排序后的顺序遍历：若当前数字 x 的一半（x/2）存在于哈希表中，则优先与其配对；否则当前数字等待配对，计入哈希表

最终哈希表为空则说明可以完成所有配对

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度，主要来自排序

空间复杂度：O(n)，哈希表存储最多 n 个元素

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        // 使用哈希表统计每个数字的出现次数
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : arr) {
            count.merge(num, 1, Integer::sum);
        }

        // 按绝对值从小到大排序
        Integer[] keys = count.keySet().toArray(new Integer[0]);
        Arrays.sort(keys, Comparator.comparingInt(Math::abs));

        // 贪心配对
        for (int key : keys) {
            int cnt = count.getOrDefault(key, 0);
            if (cnt == 0) {
                continue;
            }

            // 尝试与 key * 2 配对
            int doubleKey = key * 2;
            if (count.getOrDefault(doubleKey, 0) < cnt) {
                return false;
            }

            count.put(doubleKey, count.get(doubleKey) - cnt);
            count.put(key, 0);
        }

        return true;
    }
}

func canReorderDoubled(arr []int) bool {
    // 使用哈希表统计每个数字的出现次数
    count := make(map[int]int)
    for _, num := range arr {
        count[num]++
    }

    // 收集所有键并按绝对值排序
    keys := make([]int, 0, len(count))
    for k := range count {
        keys = append(keys, k)
    }
    sort.Slice(keys, func(i, j int) bool {
        return abs954(keys[i]) < abs954(keys[j])
    })

    // 贪心配对
    for _, key := range keys {
        cnt := count[key]
        if cnt == 0 {
            continue
        }

        // 尝试与 key * 2 配对
        doubleKey := key * 2
        if count[doubleKey] < cnt {
            return false
        }

        count[doubleKey] -= cnt
        count[key] = 0
    }

    return true
}

func abs954(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表、数组
2007. 从双倍数组中还原原数组	中等	哈希表、排序、贪心
1657. 确定两个字符串是否接近	中等	哈希表、字符串
532. 数组中的 k-diff 数对	中等	哈希表、排序
1010. 总持续时间可被 60 整除的歌曲	中等	哈希表、数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/13201592