954.md

Array of Doubled Pairs

题目

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1: Input: [3,1,3,6] Output: false

Example 2: Input: [2,1,2,6] Output: false

Example 3: Input: [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: [1,2,4,16,8,4] Output: false

给定一个偶数长度的数组，检测数组是否能通过重排列使得偶数位置的是奇数位置的两倍。

难点在于处理负数，以及如果使用map提高检测速度。
    使用一个map[int]int, key表示某个数的倍数，如果map[num]存在了则表示这个num是另外一个double，则可以将map[num]-- 表示这个数被用过了一次，就少了一次。
    如果按照上述逻辑 有两个数但较大的数num2排在num1前面, num2先寻找发现他不是其他数的两倍，则map[num2]++，再检测num1的时候也不是其他数的两倍map[num1]++。这种情况就是错的因为存在一种可能就是num1*2==num2。
    所以需要将数组排序之后再进行上述逻辑，并且负数得从后往前找回来，整数从前往后找。

代码

func canReorderDoubled(A []int) bool {
    mp := make(map[int]int, 0)
    sort.Ints(A)
    split := 0
    for split = 0; split < len(A); split++ {
        if A[split] >= 0 {
            break
        }
    }
    for cur := split-1; cur >= 0; cur-- {
        if _, ok := mp[A[cur]]; ok {
            mp[A[cur]]--
            if mp[A[cur]] == 0 {
                delete(mp, A[cur])
            }
            continue
        }
        mp[A[cur]*2]++
    }
    if len(mp) != 0 {
        return false
    }
    for cur := split; cur < len(A); cur++ {
        if _, ok := mp[A[cur]]; ok {
            mp[A[cur]]--
            if mp[A[cur]] == 0 {
                delete(mp, A[cur])
            }
            continue
        }
        mp[A[cur]*2]++
    }
    if len(mp) != 0 {
        return false
    }
    return true
}