标签： 数据流

LeetCode刷题【面试题 10.10】数字流的秩

2022 年 6 月 29 日 / / 0 Comments

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 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 次
Related Topics
  • 设计
  • 树状数组
  • 二分查找
  • 数据流

  • 👍 32
  • 👎 0

    • 树状数组结构直接套模板使用

    在该题中，树状数组对应下标表意为当前下标数字的出现次数

    1. track(int x) 方法，每读入一个数字都会调用该方法, 等价于在给树状数组对应下标数值加1，即当前下标出现次数加1
    2. getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数，等价于求下标0到当前下标的前缀和，即从0到当前下标的所有数字出现次数之和

    代码

    class StreamRank {

    private FenwickTree fenwickTree;


    public StreamRank() {
        fenwickTree = new FenwickTree(50001);
    }

    public void track(int x) {
        fenwickTree.add(x+1,1);
    }

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


    class FenwickTree{
        int[] arr;
        public FenwickTree(int num){
            arr = new int[num+1];
        }

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

        public void add(int idx, int num){
            while (idx < arr.length){
                arr[idx] += num;
                idx += lowBit(idx);
            }
        }

        public int query(int idx){
            int sum = 0;
            while (idx > 0){
                sum += arr[idx];
                idx -= lowBit(idx);
            }
            return sum;
        }
    }
}

    LeetCode刷题【剑指 Offer 41】数据流中的中位数

    2022 年 3 月 18 日 / / 0 Comments

    如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

    例如，

    [2,3,4] 的中位数是 3

    [2,3] 的中位数是 (2 + 3) / 2 = 2.5

    设计一个支持以下两种操作的数据结构：

    • void addNum(int num) – 从数据流中添加一个整数到数据结构中。
    • double findMedian() – 返回目前所有元素的中位数。

    示例 1：

    输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

    示例 2：

    输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

     

    限制：

    • 最多会对 addNum、findMedian 进行 50000 次调用。

    注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

    Related Topics
  • 设计
  • 双指针
  • 数据流
  • 排序
  • 堆（优先队列）

  • 👍 281
  • 👎 0

    • 【双薯片桶算法】又见薯片桶

    本来其实看到困难题有点多想，不过回想了下之前做的这题，我的题解剑指 Offer 09. 用两个栈实现队列（简单） ， 再想想这题，好像….也没那么复杂了

    借一次之前的图

    我们需要的其实是一个队列。但是和之前不同的是这次是有序的，我们要从这个有序队列中取中间那个值。

    这样，我们把原来的两个栈换成两个堆，一个大顶堆，一个小顶堆，那么对应这上面这个图

    1. 左边一个大顶堆，堆顶是最大值
    2. 右边一个小顶堆，堆顶是最小值
    3. 每插入一个值的时候判断下是应该往左边的插还是往右边插，小于等于左边的最大值，就往左边插，大于等于右边的最小值，就往右边插，只要做一个判断即可
    4. 插入之后对两个堆做一下平衡，保证左边堆的数量等于右边堆的数量，或者等于右边堆的数量加1，就如同上面的两个薯片桶从左往右倒一个，或者从右往左倒一个
    5. 不同于之前的栈维护的队列，堆附带自动排序的属性，所以你可以认为把一个数字插入其中一个堆里的时候，可以自动将他排序到对应的正确位置，这是一个比较智能的薯片桶
    代码
    class MedianFinder {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    /** initialize your data structure here. */
    public MedianFinder() {
        left = new PriorityQueue<>((a,b)-> b-a);
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (left.size()==0||num<=left.peek()){
            left.offer(num);
        }else{
            right.offer(num);
        }
        if (left.size() - right.size()>1){
            right.offer(left.poll());
        }else if (right.size() > left.size()){
            left.offer(right.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() == right.size()){
            return ((double) (left.peek() + right.peek()))/2;
        }else{
            return (double)left.peek();
        }
    }
}