题目描述
一个整数数组 original
可以转变成一个 双倍 数组 changed
,转变方式为将 original
中每个元素 值乘以 2 加入数组中,然后将所有元素 随机打乱 。
给你一个数组 changed
,如果 change
是 双倍 数组,那么请你返回 original
数组,否则请返回空数组。original
的元素可以以 任意 顺序返回。
思路
一个简单朴素的思路是对 changed
数组进行排序,然后从小到大做消消乐。具体来说,在排序过后的数组中进行遍历,使用一个哈希表记录被消去的元素的数量。
在遍历时,最小的元素肯定不会被消去,那么它的两倍的数字就会被添加进哈希表中。在遍历到对应的数字时,如果这个数字在哈希表中就给相应的哈希表值减一,减到零时删去哈希表中的元素即可。
最终代码:
仔细想想,我们将要被消去的值存放进了哈希表中,而且值的消去是先入先出的,那么我们其实可以用队列代替哈希表(或者说哈希表做到了队列的效果)。
使用队列替代哈希表的做法也很简单,之前是 num
在哈希表中的时候删除,那么我们的做法就是 num
在队列头部的时候弹出。如果在遇到某一个 num
的时候队列非空且 num
的值大于队列首的值,因为后面的值只会大不会小,因此返回代表错误的空列表。
最终代码:
上面两种方法的时间复杂度都在 的程度,瓶颈都出现在排序中,那么有没有可能不排序呢?当然可以,如果不排序的话,做法类似于 128. 最长连续序列。
首先用一个哈希表 ct
记录所有数字的出现次数,然后用另一个哈希集合 done
表示某个数字是否以及处理完成。遍历 ct
中的 key
进行处理即可。
因为 0 的倍数始终是 0,因此对于要做特殊处理。
而对于其他数字的处理方式是:
- 如果这个数字已经处理完了,跳过;
- 如果这个数字是偶数而且它除二的值在
ct
中,跳过; - 否则的话进行处理
- 假设这个数字一共
cnt_num
个,它的倍数一共ct[num * 2]
个,- 显然当
cnt_num < ct[num * 2]
时,还有数字没有对应的双倍,返回空列表; - 等于的话正好匹配完;
- 小于的话还有一些二倍的值。
- 显然当
- 在扩展
ans
之后,去处理num
的倍数情况,如果正好匹配完的话乘 4,否则就乘 2。
- 假设这个数字一共
最终代码: