最小的k个数

题目描述

思路

快速排序

注意本题对返回结果的顺序性没有要求，可以根据基准点来提高效率

当基准点==k，直接返回

当基准点>k，往左递归

否则往右递归

代码实现

class Solution {
    int k=0;
    public int[] getLeastNumbers(int[] arr, int k) {
        this.k=k;
        if(arr.length<=k){
            return arr;
        }
        quickSort(arr,0,arr.length-1);
        return Arrays.copyOf(arr,k);
    }
    public void quickSort(int[]arr,int l,int r){
        if(l>=r){
            return;
        }

        int i=l,j=r;
        int tmp=arr[i];
        while(i<j){
            while(i<j&&arr[j]>=arr[l])j--;
            while(i<j&&arr[i]<=arr[l])i++;
            tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }
        arr[i]=arr[l];
        arr[l]=tmp;
        if(i==k){
            return;
        }else if(i<k){
            quickSort(arr,i+1,r);
        }else{
            quickSort(arr,l,i-1);
        }
    }

}

复杂度分析

时间复杂度

快排平均O(NlogN)，最坏O(N^2)

空间复杂度

最坏O(N)，整个数组完全逆序的情况

反思不足

思路

没有想到利用数组的无序优化，事出反常必有妖，既然返回结果可以无需，那么便可以成为优化的突破口

java se

Arrays.copyOf(E [] es,int k)可以复制数组的前k个元素

数据流的中位数

题目描述

思路

虽然是一道困难题，但是解题思路却是很简单的，排序，然后按要求取数即可，排序我们可以取数时一次性排，也可以在加入时就让其有序

优先队列/堆

我们注意到中位数其实是可以将数据对半分的，因此可以考虑以中位数为堆顶，构建大小根堆，查中位数时返回堆顶元素

显然需要让一个堆的元素在奇数时比另一个多1

代码实现

class MedianFinder {
    Queue<Integer> s,b;
    int cth=0;
    /** initialize your data structure here. */
    public MedianFinder() {
        s=new PriorityQueue<Integer>();
        b=new PriorityQueue<Integer>((x,y)->y-x);
    }
    
    public void addNum(int num) {
        cth++;
        if(cth%2==0){
            s.offer(num);
            b.offer(s.poll());
        }else{
            b.offer(num);
            s.offer(b.poll());
        }
    }
    
    public double findMedian() {
        if(cth%2==0){
            return (s.peek()+b.peek())/2.0;
        }else{
            return s.peek();
        }
    }
}

复杂度分析

时间复杂度

O(logN),堆数据结构的弹出插入操作的时间复杂度，不知道去学数据结构

空间复杂度

O(N)

反思不足

思路

java se

PriorityQueue类是java中的优先队列，默认为小根堆，可以传lambda表达式改为大根堆