TOPk问题

1. 最大的k个：快排、大小堆

1. 快排解决
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        /*
        最小的k个数
        8.24
        */

        //1. 快排：
        //2. 小根堆、大根堆
        //3. quickSelect

        quickSort(arr,0,arr.length-1);

        return Arrays.copyOfRange(arr,0,k);
    }

    public void quickSort(int[] nums,int start,int end){
        
        if(start > end){
            return;
        }

        int pivot = getPivot(nums,start,end);
        quickSort(nums,start,pivot-1);
        quickSort(nums,pivot+1,end);
    }

    public int getPivot(int[] nums,int start,int end){
        int pivot = nums[start];
        int left = start;
        int right = end;

        while(left <= right){
            while(left <= right && nums[left] <= pivot){
                left++;
            }
            while(left <= right && nums[right] > pivot){
                right--;
            }

            if(left < right){
                swap(nums,left,right);
            }
        }
        swap(nums,start,right);
        return right;
    }
    
    public void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}


2. 小根堆
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        //最小堆和最大堆速度应该差不多
        int len = arr.length;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(len,(a,b) -> (a-b));
        for(int i=0;i<len;i++){
            minHeap.add(arr[i]);
        }

        int[] result = new int[k];
        //弹出前k个
        for(int i=0;i<k;i++){
            result[i] = minHeap.poll();
        }
        return result;
    }
}


3. quickSelect
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        /*
        TOPK
        8.6
        */
        //最优解，quickselect，时间复杂度On

        quickselect(arr,0,arr.length-1,k);

        return Arrays.copyOfRange(arr,0,k);
    }

    public void quickselect(int[] arr,int start,int end,int k){
        if(start == end){
            return;
        }

        int left = start;
        int right = end;
        int pivot = arr[start];

        while(left <= right){
            while(left <= right && arr[left] < pivot){
                left++;
            }
            while(left <= right && arr[right] > pivot){
                right--;
            }
            if(left <= right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }

        if(start <= k && k <= right){
            quickselect(arr,start,right,k);
        }
        if(left <= k && k <= end){
            quickselect(arr,left,end,k);
        }
    }
}

2. 第k大元素：快选

class Solution {
    public int findKthLargest(int[] nums, int k) {
        /*
        第k大元素
        8.24
        */

        //传入len-k表示最大k
        quickSelect(nums,0,nums.length-1,nums.length-k);

        return nums[nums.length-k];
    }

    public void quickSelect(int[] nums,int start,int end,int k){
        if(start == end){
            return;
        }

        int pivot = nums[start];
        int left = start;
        int right = end;

        while(left <= right){
            while(left <= right && nums[left] < pivot){
                left++;
            }
            while(left <= right && nums[right] > pivot){
                right--;
            }
            if(left <= right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }

        if(left <= k && k <= end){
            quickSelect(nums,left,end,k);
        }
        if(start <= k && k <= right){
            quickSelect(nums,start,right,k);
        }
    }
}


//大根堆
class Solution {
    public int findKthLargest(int[] nums, int k) {
        /*
        第k大个数
        8.24
        */

        //最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(nums.length,(a,b) -> (b-a));

        //存入
        for(int i=0;i<nums.length;i++){
            maxHeap.add(nums[i]);
        }

        //弹出前k-1个
        for(int i=0;i<k-1;i++){
            maxHeap.poll();
        }

        return maxHeap.poll();
    }
}

3. 前k个高频元素：大根堆存入map.keySet()，根据map.get()排序

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        /*
        前k个高频元素
        8.24
        */

        //大根堆根据map.get()排序，存入keySet

        //hashmap先存入
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }

        //根据map.get()倒序排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length,(a,b) -> (map.get(b) - map.get(a)));

        //存入keySet
        for(int i : map.keySet()){
            queue.add(i);
        }

        //弹出前k个
        int[] result = new int[k];
        for(int i=0;i<k;i++){
            result[i] = queue.poll();
        }

        return result;
    }
}