题目

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。

请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:输入: ["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"] [[], [1], [0], [0]]

输出: [null,0,null,1]

提示：x <= 50000

track 和 getRankOfNumber 方法的调用次数均不超过 2000 次

解题思路分析

1、树状数组；时间复杂度O(nlog(n))，空间复杂度O(n)

type StreamRank struct {
   length int
   c      []int
}

func Constructor() StreamRank {
   return StreamRank{
      length: 50002,
      c:      make([]int, 50003),
   }
}

func (this *StreamRank) Track(x int) {
   this.upData(x+1, 1)
}

func (this *StreamRank) GetRankOfNumber(x int) int {
   return this.getSum(x + 1)
}

func (this *StreamRank) lowBit(x int) int {
   return x & (-x)
}

// 单点修改
func (this *StreamRank) upData(i, k int) { // 在i位置加上k
   for i <= this.length {
      this.c[i] = this.c[i] + k
      i = i + this.lowBit(i) // i = i + 2^k
   }
}

// 区间查询
func (this *StreamRank) getSum(i int) int {
   res := 0
   for i > 0 {
      res = res + this.c[i]
      i = i - this.lowBit(i)
   }
   return res
}

2、暴力法；时间复杂度O(n^2)，空间复杂度O(n)

type StreamRank struct {
   m map[int]int
}

func Constructor() StreamRank {
   return StreamRank{m: make(map[int]int)}
}

func (this *StreamRank) Track(x int) {
   this.m[x]++
}

func (this *StreamRank) GetRankOfNumber(x int) int {
   res := 0
   for k, v := range this.m {
      if k <= x {
         res = res + v
      }
   }
   return res
}

3、内置函数；时间复杂度O(nlog(n))，空间复杂度O(n)

type StreamRank struct {
   arr []int
}

func Constructor() StreamRank {
   return StreamRank{arr: make([]int, 0)}
}

func (this *StreamRank) Track(x int) {
   index := sort.Search(len(this.arr), func(i int) bool {
      return x <= this.arr[i]
   })
   temp := append([]int{}, this.arr[:index]...)
   temp = append(temp, x)
   temp = append(temp, this.arr[index:]...)
   this.arr = temp
}

func (this *StreamRank) GetRankOfNumber(x int) int {
   return sort.Search(len(this.arr), func(i int) bool {
      return x < this.arr[i]
   })
}

总结

Medium题目，多种解题方法，可以使用树状数组