【刷题日记】954. 二倍数对数组

本次刷题日记的第 21 篇，力扣题为：954. 二倍数对数组 ，中等

一、题目描述：

又开始了新一轮的更文，慢慢的已经养成了更文的习惯，就像运动健身一样，一日不运动身体不舒服，一日不更文，总感觉心里缺点啥，今天继续来刷一下每日一题，锻炼一下思维

今天是一个中等题，不知道是不是自带愚人节特性

二、这道题考察了什么思想？你的思路是什么？

咱们继续开始认真刷题，一起来看看力扣今天的每日一题带给我们了哪些重点的内容：

• 题目会给出一个数组 ，长度一定是偶数的，最小可以是 0 ，最大可以是 3 * 104，没懂为啥是这个最大值
• 数组里面的元素数值题目也给出来了，其实对于这个题，我们不用太过关心这个数字的范围
• 还有一个重点信息是，题目需要我们校验，数字的每一个奇数索引的值是否等于前面偶数索引的值 * 2 ，这里需要注意，题目中是说我们需要对数组进行重组，实际上我们也不需要这样做

咱们解决问题就要看到问题的本质，而不是根据问题的表象去做模拟，当然，模拟也是非常有必要的，这毕竟也是一个推敲的过程

我们可以一起来推演一下：

仔细揣摩题目中给出的意思，其实就是要我们找到成双成对的数据即可，每一对数据中的 2 个数字，其中一个数字是另外一个的 2 倍 即可，只要我们在数组中校验所有成对的数据都能够满足这样的条件，那么这个题我们就实现了

例如这样，只要找到对应的就可以了

首先，我们可能会思考，去遍历一下数组，指定数组的第一个数字，让第一个数字去和后面的每一个数字比对，只要满足条件，那么就可以向下遍历，如果不满足，那么这个数组肯定不是，那么这样一轮一轮的遍历的话，太挫了 ，肯定有更好的方式

那么，我们的编码思路可以是这样的：

• 可以将数字中的值作为一个 helper 数组中的索引，helper[arr[i]] 的值初始化为 1 即可
• 将题目给出的数组按照实际数字的绝对值来进行排序
• 开始遍历 arr 数组，去校验是否有 helper[arr[i] * 2] == 1，若是 则本次满足，若不是则 arr 整个数组不满足
• 最终看，整个数组是否满足，若是，则返回 true，否则 返回 false

接下来就是开心的翻译环节了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，注意上述说到的使用 helper 帮助数组来处理，这其实是一个 hash 表

其他的需要注意一下 helper[arr[i] * 2]  是否为 0 的细节，helper[arr[i] * 2] 为 0 ，说明，arr 数组中本次没有配对的数字

编码如下：

func canReorderDoubled(arr []int) bool {
    // 先构造一个简单的 hash 表
    helper := make(map[int]int,0)
    for _,num := range arr {
        helper[num]++
    }
    // 将数组 arr 进行排序
    sort.Slice(arr ,func(a,b int) bool {
        return int(math.Abs(float64(arr[a]))) < int(math.Abs(float64(arr[b]))) 
    })
    // 开始校验前一半的数字是否有其对应的 2 倍的数字
    for i:=0;i<len(arr);i++ {
        // 说明该数字已经被匹配过
        if helper[arr[i]] == 0 {
            continue
        }
        helper[arr[i]]--
        // 对应的 2 倍的数字置位为 0 ，表示已经匹配过
        if helper[arr[i] * 2] == 0{
            return false
        }else{
            helper[arr[i] * 2]--
        }
    }
    return true
}

根据上述编码的话，应该就很清晰了

四、总结：

本次题目的时间复杂度是 O(nlogn) ,空间复杂度是 O(n)，因为我们引入了 helper ，会占用 n 的空间消耗

原题地址：954. 二倍数对数组

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~