二倍数对数组

题目描述：

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

示例 1：

输入：arr = [3,1,3,6]
输出：false
示例 2：

输入：arr = [2,1,2,6]
输出：false
示例 3：

输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

提示：

0 <= arr.length <= 3 * 104
arr.length 是偶数
-105 <= arr[i] <= 105

思路:

时间复杂度：O(nlogn),空间复杂度O(n)

这个代码考察的是是不是所有数都是配对的，有两倍关系，所以负数降序，正书升序，然后拼接在一起判断每个数有没有两倍关系的数字。

代码:

func canReorderDoubled(arr []int) bool {
    mp := make(map[int]int, 0)
    var arr1,arr2 []int
    for _,v := range arr{
        mp[v]++
        if v <0{
            arr1 = append(arr1, v)
        }else{
            arr2 = append(arr2,v)
        }
    }
      sort.Slice(arr1, func(i, j int) bool { return arr1[i]>arr1[j] })
      sort.Ints(arr2)
    arr1 = append(arr1,arr2...)
    count := 0
    for _,v := range arr1{
        if mp[v] >0 && mp[2 * v] >0  {
            if(v == 0 && mp[v]>=2) || v != 0{
                count++
                mp[v]--
                mp[2 * v]--
            }else{
                mp[v]--
            }
            
        }
    }
    if count< len(arr)/2{
        return false
    }
    return true
}

代码效率：

执行用时：96 ms, 在所有 Go 提交中击败了44.83%的用户
内存消耗：7.1 MB, 在所有 Go 提交中击败了68.97%的用户