【刷题日记】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. 二倍数对数组
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
