想讨论一道谷歌高频题

反正都是295 Stream Median变体 具体想怎么考怎么变看考官心情

有人想过只存最大的5%和最小的5%吗， 这样可以省下很多空间， 然后用总数减去这部分的和再除以元素个数就能得到平均数。 （似乎与二楼思路差不多）

感觉是强加几个条件逼你写个pq出来。考pq的data structure的

不知道小帅 发表于 2020/01/17 02:15:58
个人觉得，可以用一个最大堆，一个最小堆，然后一个记录所有的小的数，另一个记录所有大的数。另外记录一个size，每次来一个...

这个跟之前面bat面试官给的解法一样

插眼 ..：$/@s

感觉这题其实比295，480还要简单一点。

我的想法是维护两个pq，把5%的最小数和最大数放进去。在维护一个TreeSet放中间的数
如果数据量太大，就存Pair<value, count>, 再不行就用分布式分段计算

import java.util.*;

public class Test {
    PriorityQueue<Integer> bottom;
    PriorityQueue<Integer> top;
    TreeSet<Integer> middle;
    int totalSize;
    int percentage;
    int sumOfMiddle;
    /** initialize your data structure here. */
    public Test() {
        bottom = new PriorityQueue<>((a, b)-> b.compareTo(a));
        top = new PriorityQueue<>();
        middle = new TreeSet<>();
        totalSize = 0;
        percentage = 5;
        sumOfMiddle = 0;
    }
   
    public void addNum(int num) {
        middle.add(num);
        totalSize++;
        sumOfMiddle += num;
        rebalanceBottom();
        rebalanceTop();
    }
   
    public double findAverage() {
        return (double)sumOfMiddle / middle.size();
    }

    private void rebalanceBottom() {
        int bottomSize = percentage * totalSize / 100;
        //put one more to bottomHeap
        if (bottomSize > bottom.size()) {
            int num = middle.pollFirst();
            bottom.add(num);
            sumOfMiddle -= num;
        } else {
            //same size:
            int num = middle.pollFirst(); //pull out the smallest number
            bottom.offer(num);
            sumOfMiddle -= num;
            num = bottom.poll(); //pull in the biggest value
            middle.add(num);
            sumOfMiddle += num;
        }
    }

    private void rebalanceTop() {
        int topSize = percentage * totalSize / 100;
        //put one more to topHeap
        if (topSize > top.size()) {
            int num = middle.pollLast();
            top.add(num);
            sumOfMiddle -= num;
        } else {
            //same size:
            int num = middle.pollLast(); //pull out the largest number
            top.offer(num);
            sumOfMiddle -= num;
            num = top.poll(); //pull in the smallest value
            middle.add(num);
            sumOfMiddle += num;
        }
    }

    public static void main(String args[]) {
      Test t = new Test();
      for (int i = 0; i < 200; i++) {
        t.addNum(i);
        System.out.println("i=" +i+ ", avg="+ t.findAverage());
        System.out.print("number removed in top: ");
        for (int j: t.top) {
          System.out.print(j + " ");
        }
        System.out.println();
        
        System.out.print("number removed in bottom: ");
        for (int j: t.bottom) {
          System.out.print(j + " ");
        }
        System.out.println();
      }
      for (int i = 100; i >= 0; i--) {
        t.addNum(i);
        System.out.println("i=" +i+ ", avg="+ t.findAverage());
        System.out.print("number removed in top: ");
        for (int j: t.top) {
          System.out.print(j + " ");
        }
        System.out.println();
        
        System.out.print("number removed in bottom: ");
        for (int j: t.bottom) {
          System.out.print(j + " ");
        }
        System.out.println();
      }
   }
}

不知道小帅 发表于 2020-1-17 02:15
个人觉得，可以用一个最大堆，一个最小堆，然后一个记录所有的小的数，另一个记录所有大的数。另外记录一个 ...

size是维持在所有输入的10%吗？怎么样计算剩下90%的平均数呢？

开一个BST，维护一个mean，total number of integers，number of integers in BST
每有一个新integer，进树，更新mean和两个number，然后看要不要从BST里去除最大最小数，如果不用就不管，如果用就去掉，更新树和number

之后可以想下怎么把BST中间的那部分放进disk里

O(log(k)) 的解法以及步骤，大家看看哪里不对：

1. 使用最近的 k 个元素建立一个哈希表，其中键为该元素的 index，值为该元素的（值，index）组成的 tuple。
2. 使用最近的 k 个元素的（值，index）组成的 tuple 组成一个二叉平衡树（Treaps，红黑树），其中每个节点都记录左右子树的节点个数以及和。
3. 当有新的元素加入的时候，通过哈希表找到需要删除的旧 index 对应的 tuple，在二叉平衡树找到该 tuple 并删除，更新相应子树的记录。
4. 把新元素插入到哈希表以及二叉平衡树，并更新相应的子树记录。
5. 在二叉平衡树总查找第 5% 大 以及第 95% 大的元素，并用根节点的总和减去它们分别左右子树的值。得到结果

djmiss 发表于 2020-2-6 08:05
感觉这题其实比295，480还要简单一点。

我的想法是维护两个pq，把5%的最小数和最大数放进去。在维护一个 ...

你不需要从树或者最大最小堆中删除旧的无效的元素吗？