题目为leetcode 383题， https://leetcode.com/problems/ransom-note
using map: 12ms, faster than 62.24%
```
func canConstruct(ransomNote string, magazine string) bool {
m := make(map[rune] int, 0)
for _, v := range magazine {
m[v]++
}
for _, v := range ransomNote {
m[v]--
if m[v] < 0 {
return false
}
}
return true
}
```
using array, 0ms faster than 100%
```
func canConstruct(ransomNote string, magazine string) bool {
m := make([] int, 26)
for _, v := range magazine {
m[v - 'a']++
}
for _, v := range ransomNote {
m[v - 'a']--
if m[v - 'a'] < 0 {
return false
}
}
return true
}
```
使用这两种数据结构结果差这么多原因是什么呢，有大神可以科普下吗
我觉得应该是因为数组在内存中线性连续的.所以用接近常量v-a的定位算法速度最快.这里的算法效率是o(1).
而map在内存中存储并不是线性连续的,而且要经过hash计算index所以就慢了一些.虽然hash也是o(1)的效率但是在计算步骤上要比v-a复杂, 所以速度上不如.
#1
更多评论
slclub
坚持就是胜利
使用时，看元素的多少，元素少，数组是最快的，无论是查找，各种操作都优秀与 map
要是元素比较多，1000个以上吧，那 map的性能要明显优异与数组了，毕竟hash 计算的占时长是固定的。 而数组遍历查 越多肯定越慢哦。
这里就性能而言不能完全看时间复杂度； 虽然O(1) 这是理论值，还有计算找位置呢是要花时间的 。
#2
今日阅读排行
一周阅读排行