力扣 954. 二倍数对数组 暴力破解

题目

想法

分析题目

这道题不是很复杂，但是题目对于我来说，比较难懂，我按照我的理解复述一下

对于数组而言，满足以下条件则返回true，否则返回 false

1. 找出数组中能够组成倍数的数，例如 [1,2] , [2,4] , [0,0]
2. 找出的倍数是数组长度的一半
3. 数组中的每个数只能用一次

举个栗子

例子1

对于数组

arr = [4,-2,2,-4] 其长度为 4

可以组成 [2,4] , [-2,-4]2组，数组中的数据仅用了一次

组成的对数 正好是 数组长度的 一半 ， 即: 2 = 4/2

所以返回 true

例子2

对于数组arr = [1,2,4,16,8,4] 其长度为 6

可以组成 [1,2]``[4,8] 或者 [1,2],[8,16] 2组 ，数组中的数据仅能使用一次

组成的对数 不等于 数组长度的一半 ， 即: 2 != 6/2

所以返回 false

解决方法

想法

我们可以遍历整个数组，去找该数组中是否有自己2倍的数据，若有，在对数增加1 ，并且删除 这2个数据 即可。

即

对于如下数组

第一次遍历: -2

我们计算 -2 的倍数 为 -4, 并且查询 -4 存在于数组，则删除这2个元素，并且对数计数器增加1 为 1

即

数据遍历完毕后，我们计算得知 对数计数器 == 数组长度 / 2, 所以，该返回 true

但是也有例外

对于如下数组

如果按照从前往后遍历，则只能返回 2对

但是如果按照这样来遍历，则能够返回 3对

所以数组，应该提前排序。

解决方案

我们可以将数组的值 和 出现的次数建立一个 hash map

然后遍历排序后的数组 ， 计算其倍数值，再在map中查询，若查询到，则将 map 中的2个数据(遍历的数据本身 和 倍数) 各自减去1，并且使 对数计算器 + 1 ,

遍历完成后，我们计算 对数计数器 和 数组长度/2 是否相等 就行了。

对于上诉案例，我们可以定义为map , 其值为出现的次数

然后我们再进行遍历，再删减相应的值即可，最后 计算是否相等，不过需要注意的是，我在提交中，遇到一个问题: 如果出现的是0 ，则需要判断0的次数是否出现为大于等于2次，因为 0的倍数依然是0

代码

func delwithMap(arrMap map[int]int , val int) () {
  if arrMap[val] > 1 {
    arrMap[val] = arrMap[val] - 1
  } else {
    delete(arrMap,val)
  }
}
func canReorderDoubled(arr []int) bool {
  arrMap := make(map[int]int,1)
  sort.Ints(arr)
  for i:=0;i<len(arr);i++ {
    arrMap[arr[i]] = arrMap[arr[i]] + 1
  }
  count := 0
  for i:=0;i<len(arr);i++ {
    _ , ok := arrMap[arr[i]];if ok {
      _ , ok1 := arrMap[arr[i] * 2]; if ok1 {
        if arr[i] == 0 {
          if 1 < arrMap[0] {
            count++
          }
        } else {
          count++
        }
        delwithMap(arrMap,arr[i])
        delwithMap(arrMap,arr[i]*2)
      }
    }
  }
  if count == len(arr) / 2 {
    return true
  }
  return false
}