数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)，意思是在数组里下标0~3这个范围上，有几个2？答案返回2。假设给你一个数组arr， 对这个数组的查询非常频繁，都给出来。请返回所有查询的结果。
遍历存map。map的键是数组中的值，map的值是存数组下标的数组。比如{3,2,2,3,1}，保存到map里就是{3:[0,3],2:[0,1],1:[4]}，然后用二分法查找某个数的索引范围。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{3, 2, 2, 3, 1}
box := NewQueryBox2(arr)
ret := box.query(0, 3, 2)
fmt.Println(ret)
}
type QueryBox2 struct {
dataMap map[int][]int
}
func NewQueryBox2(arr []int) *QueryBox2 {
ret := &QueryBox2{}
ret.dataMap = make(map[int][]int)
for i := 0; i < len(arr); i++ {
ret.dataMap[arr[i]] = append(ret.dataMap[arr[i]], i)
}
return ret
}
func (this *QueryBox2) query(L int, R int, value int) int {
if _, ok := this.dataMap[value]; !ok {
return 0
}
indexArr := this.dataMap[value]
// 查询 < L 的下标有几个
a := this.countLess(indexArr, L)
// 查询 < R+1 的下标有几个
b := this.countLess(indexArr, R+1)
return b - a
}
// 在有序数组arr中，用二分的方法数出<limit的数有几个
// 也就是用二分法，找到<limit的数中最右的位置
func (this *QueryBox2) countLess(arr []int, limit int) int {
L := 0
R := len(arr) - 1
mostRight := -1
for L <= R {
mid := L + ((R - L) >> 1)
if arr[mid] < limit {
mostRight = mid
L = mid + 1
} else {
R = mid - 1
}
}
return mostRight + 1
}执行结果如下：
