咸糖记录编程的地方

念念不忘,必有回响。

目录
数据结构 2.栈、队列、堆
/  

数据结构 2.栈、队列、堆 有更新!

232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.push(x)
* Push element x to the back of queue.pop()
* Removes the element from in front of queue.peek()
* Get the front element.empty()
* Return whether the queue is empty.

Example:


MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

这里我采用的是双栈法
入栈的时间复杂度是O(1)

出栈的时间复杂度是O(N)

我们采用一个top 去记录栈底部的数据,然后移动栈的时候当栈1的容量为0 这个元素就是top

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    private int top = -1;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if(stack1.size()==0) top = x;
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        while(stack1.size()!=0){
         stack2.push(stack1.pop());
        }
        int res = stack2.pop();
        while(stack2.size()!=0){
            push(stack2.pop());
        }
        return res;
    }
    
    /** Get the front element. */
    public int peek() {
        return top;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

我采用的是分治的方法解决这个问题也可以采用MInheap来完成
就是选择第一个字符作为基准,将比这个大的数字放在他前面,比他小的放在他后面 然后交换到数组中央。
这样他所在的坐标对应的值就是他的第 坐标+1 大的数
如果k 比 当前索引大 就继续寻找左边,比当前索引小 就继续寻找右边。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums==null || nums.length == 0) return 0;
        int left = 0;
        int right = nums.length-1;
        while(true){
            int pos = partition(nums,left,right);
            if(pos+1 == k){
                return nums[pos];
            }
            else if(pos +1>k){
                right = pos-1;
            }else
                left = pos+1;
        }
    }
    
    private int partition(int[] nums,int left,int right){
        int pivot = nums[left];
        int l = left+1;
        int r = right;
        while(l<=r){
            if(nums[l]<pivot && nums[r]>pivot){
                swap(nums,l++,r--);
            }
            if(nums[l]>=pivot) l++;
            if(nums[r]<=pivot) r--;
        }
        swap(nums,left,r);
            return r;
    }
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

295. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value.

So the median is the mean of the two middle value.

For example:

[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:
* void addNum(int num) - Add a integer number from the data stream to the data structure.
* double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

这道中位数的题目我是采用最小堆和最大堆做的

一个最大堆保存一半较小的数据
另一个最小堆保存一半较大的数据

然后采取平衡手段保证两个堆的大小差小于2


class MedianFinder {
   private PriorityQueue<Integer> l;
    private PriorityQueue<Integer> r;
    /** initialize your data structure here. */
    public MedianFinder() {
        r = new PriorityQueue<Integer>();
        l = new PriorityQueue<Integer>(new Comparator<Integer>(){ //大顶堆,容量11
            @Override
            public int compare(Integer i1,Integer i2){
                return i2-i1;
            }
        });
    }

    public void addNum(int num) {
        if(l.size() == 0 || num<=l.peek()){
            l.add(num);
        }
        else {
            r.add(num);
        }
        if(l.size()<r.size()){
            l.add(r.poll());
//            r.remove();
        }else if(l.size() - r.size() ==2){
            r.add(l.poll());
//            l.remove();
        }

    }

    public double findMedian() {
        if(l.size()>r.size()){
            return l.peek();
        }
        else{
            double res = ((double)l.peek()+(double)r.peek())/2;
            return res;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */



标题: 数据结构 2.栈、队列、堆
作者:xiantang
地址:http://xiantang.info/articles/2019/06/03/1559551218338.html

评论