问题描述
Given an integer array of even length arr, return true if it is possible to reorder arr such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2, or false otherwise.
Example 1:
Input: arr = [3,1,3,6]
Output: false
Example 2:
Input: arr = [2,1,2,6]
Output: false
Example 3:
Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
Example 4:
Input: arr = [1,2,4,16,8,4]
Output: false
Constraints:
- 2 <= arr.length <= 3 * 10^4
- arr.length is even.
- -10^5 <= arr[i] <= 10^5
问题分析
问题的要求是能否将给定数组分成两两一组，每一组的2个元素中，其中一个元素是另一个的2倍。
先简单考虑，假设数组中均为非负数；排序后，从小的元素开始，查找它的2倍是否存在：
- 如果不存在，则直接返回false；
- 如果存在，将当前元素和它的2倍从原数组中移除；继续判断
如果按照这种方式，能够一直查找到数组为空，说明符合题目要求，返回true即可。
而对于负数，稍微麻烦一些；依然是从小的元素开始，我们查找它的1/2是否存在；且查找之前，可以先判断下当前元素是否为奇数； 如果为奇数，必定不符合要求
由于整个过程中，我们需要频繁判断某个数是否存在，且“使用”完了还得从原数组移除。那么我们可以通过map记录每个数出现的次数，“使用”后对应的数量减1；如果数不存在，或者存在但是可用数量小于等于0，则返回false
综上，解法如下
示例代码
func canReorderDoubled(arr []int) bool {
// base case
if len(arr) == 0 {
return true
}
// 统计每个数字出现的次数
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
m[arr[i]]++
}
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j]
})
for i := 0; i < len(arr); i++ {
if m[arr[i]] <= 0 {
continue
}
// 如果为负数，查找 arr[i] / 2 是否存在， 且数量是否大于0
if arr[i] < 0 {
// 如果存在奇数，说明arr[i]的2倍数量不足，最后必定无法配对
if arr[i]%2 != 0 {
return false
}
// 如果arr[i]/2不存在；或者剩余可用数量小于0
if _, ok := m[arr[i]/2]; !ok || m[arr[i]/2] <= 0 {
return false
}
// 消耗数量减1
m[arr[i]/2]--
} else {
// 如果arr[i] * 2 不存在，或者剩余可用数量小于0
if _, ok := m[arr[i]*2]; !ok || m[arr[i]*2] <= 0 {
return false
}
// 消耗数量减1
m[arr[i]*2]--
}
// 当前遍历的数字消耗数量减1
m[arr[i]]--
}
return true
}