Question

面试题 10.10. 数字流的秩

English Version

题目描述

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 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 次

解法

方法一：树状数组

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：

1. 单点更新 update(x, delta)： 把序列 x 位置的数加上一个值 delta；
2. 前缀和查询 query(x)：查询序列 [1,...x] 区间的区间和，即位置 x 的前缀和。

这两个操作的时间复杂度均为 $O(\log n)$。

树状数组最基本的功能就是求比某点 x 小的点的个数（这里的比较是抽象的概念，可以是数的大小、坐标的大小、质量的大小等等）。

比如给定数组 a[5] = {2, 5, 3, 4, 1}，求 b[i] = 位置 i 左边小于等于 a[i] 的数的个数。对于此例，b[5] = {0, 1, 1, 2, 0}。

解决方案是直接遍历数组，每个位置先求出 query(a[i])，然后再修改树状数组 update(a[i], 1) 即可。当数的范围比较大时，需要进行离散化，即先进行去重并排序，然后对每个数字进行编号。

class BinaryIndexedTree:
  def __init__(self, n):
    self.n = n
    self.c = [0] * (n + 1)

  @staticmethod
  def lowbit(x):
    return x & -x

  def update(self, x, delta):
    while x <= self.n:
      self.c[x] += delta
      x += BinaryIndexedTree.lowbit(x)

  def query(self, x):
    s = 0
    while x > 0:
      s += self.c[x]
      x -= BinaryIndexedTree.lowbit(x)
    return s


class StreamRank:
  def __init__(self):
    self.tree = BinaryIndexedTree(50010)

  def track(self, x: int) -> None:
    self.tree.update(x + 1, 1)

  def getRankOfNumber(self, x: int) -> int:
    return self.tree.query(x + 1)


# Your StreamRank object will be instantiated and called as such:
# obj = StreamRank()
# obj.track(x)
# param_2 = obj.getRankOfNumber(x)

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }

  public static int lowbit(int x) {
    return x & -x;
  }

  public void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += lowbit(x);
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= lowbit(x);
    }
    return s;
  }
}

class StreamRank {
  private BinaryIndexedTree tree;

  public StreamRank() {
    tree = new BinaryIndexedTree(50010);
  }

  public void track(int x) {
    tree.update(x + 1, 1);
  }

  public int getRankOfNumber(int x) {
    return tree.query(x + 1);
  }
}

/**
 * Your StreamRank object will be instantiated and called as such:
 * StreamRank obj = new StreamRank();
 * obj.track(x);
 * int param_2 = obj.getRankOfNumber(x);
 */

class BinaryIndexedTree {
public:
  int n;
  vector<int> c;

  BinaryIndexedTree(int _n)
    : n(_n)
    , c(_n + 1) {}

  void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += lowbit(x);
    }
  }

  int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= lowbit(x);
    }
    return s;
  }

  int lowbit(int x) {
    return x & -x;
  }
};

class StreamRank {
public:
  BinaryIndexedTree* tree;

  StreamRank() {
    tree = new BinaryIndexedTree(50010);
  }

  void track(int x) {
    tree->update(x + 1, 1);
  }

  int getRankOfNumber(int x) {
    return tree->query(x + 1);
  }
};

/**
 * Your StreamRank object will be instantiated and called as such:
 * StreamRank* obj = new StreamRank();
 * obj->track(x);
 * int param_2 = obj->getRankOfNumber(x);
 */

type BinaryIndexedTree struct {
  n int
  c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  c := make([]int, n+1)
  return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
  return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
  for x <= this.n {
    this.c[x] += delta
    x += this.lowbit(x)
  }
}

func (this *BinaryIndexedTree) query(x int) int {
  s := 0
  for x > 0 {
    s += this.c[x]
    x -= this.lowbit(x)
  }
  return s
}

type StreamRank struct {
  tree *BinaryIndexedTree
}

func Constructor() StreamRank {
  tree := newBinaryIndexedTree(50010)
  return StreamRank{tree}
}

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

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

/**
 * Your StreamRank object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Track(x);
 * param_2 := obj.GetRankOfNumber(x);
 */