7_堆.md

堆

1、字符流中第一个不重复的字符

字符流中第一个不重复的字符

//统计字符出现的次数
private int[] freq = new int[256];
//队列中只存储出现一次的字符，并且出队顺序就是入队顺序
private Queue<Character> queue = new LinkedList<>();
//Insert one char from stringstream
public void Insert(char ch) {
    freq[ch]++;
    queue.offer(ch);

    //队列中只存储出现一次的字符
    while (!queue.isEmpty() && freq[queue.peek()]>1){
        queue.poll();
    }
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
    return queue.isEmpty()? '#':queue.peek();
}

2、数据流中的中位数

数据流中的中位数

private int n;//当前数据流元素数

//大根堆，维护数组左边元素
private PriorityQueue<Integer> left = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
});

//小根堆，维护数组右边元素。右边元素均大于左边元素
private PriorityQueue<Integer> right = new PriorityQueue<>();

public void Insert(Integer num) {
    /* 插入要保证两个堆存于平衡状态 */
    if(n%2==0){
        //注意：这里 left 先加入 num,然后又将最大值加入到 right 中。
        //left 的长度没有变化，right 中添加一个元素
        left.add(num); //插入大根堆中
        right.add(left.poll()); // left.poll() 是左侧的最大值
    }else{
        right.add(num);
        left.add(right.poll());
    }
    n++;
}

public Double GetMedian() {
    if(n%2==0){ // n 是偶数
        return (left.peek()+right.peek())/2.0;
    }else{ // n 是奇数，注意是奇数时，中位数被放入到 right 中（是 insert 操作而定）
        return (double)right.peek();
    }
}

3、滑动窗口的最大值

滑动窗口的最大值

// 思路一：暴力解法
// 时间复杂度 O(N^2)

public ArrayList<Integer> maxInWindows(int [] num, int size){
    ArrayList<Integer> res = new ArrayList<>();
    if(size<=0 || num.length<size){
        return res;
    }

    for(int i=0;i<=num.length-size;i++){
        res.add(getMax(num,i,i+size-1));
    }
    return res;
}

private int getMax(int[] nums,int start,int end){
    int res=nums[start];
    for(int i=start+1;i<=end;i++){
        res = Math.max(res,nums[i]);
    }
    return res;
}

//思路二：维护一个大小为 size 的大根堆

public ArrayList<Integer> maxInWindows(int [] num, int size){
    ArrayList<Integer> res = new ArrayList<>();
    if(size<=0 || num.length<size){
        return res;
    }

    //维护一个大小为 size 的大根堆
    PriorityQueue<Integer> pq = new PriorityQueue<>(size, 
        new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            int num = o2-o1;
            return num;
        }
    });

    //将一个滑动窗口的数据加入到大根堆中
    for(int j=0;j<size;j++){
        pq.add(num[j]);
    }
    res.add(pq.peek()); // 堆顶元素就是该滑动窗口的最大元素

    for(int i=0,j=size;j<num.length;i++,j++){
        //滑动窗口向右边移动，则会先删除最左边的元素，然后添加右边元素
        //注意：滑动窗口的长度是固定的，
        pq.remove(num[i]);
        pq.add(num[j]);
        res.add(pq.peek());
    }
    return res;
}

4、最小的 k 个数

最小的 k 个数

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    if(k<=0 || k>input.length){
        return new ArrayList<>();
    }

    //使用大根堆
    PriorityQueue<Integer> queue = new PriorityQueue<>(
        new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

    for(int num : input){
        queue.add(num);
        if(queue.size()>k){
            queue.poll();
        }
    }
    return new ArrayList<>(queue);
}