NC88 寻找第K大（快速排序和堆排序）

爱被打了一巴掌 2022-09-16 14:23 105阅读 0赞

快速排序做法

import java.util.*;
    
    public class Solution {
        
        public int findKth(int[] a, int n, int K) {
        
            // write code here
            QuickSort(a,0,n-1); // 快速排序
            return a[n-K];  //返回第k大的数字
            
        }
        
        // 快速排序
        public void QuickSort(int[] arr,int left,int right){
        
            // 跳出递归的条件
            if(left>right){
        
                return;
            }
            int base=arr[left];  // 基准值
            int i=left;  //i从左往右移动
            int j=right;  //j从右往左移动
            while(i < j){
        
                //j要找到比base小的数字才能停下
                while(arr[j]>=base && i<j){
        
                    j--;
                }
                //i要找到比base大的数字才能停下
                while(arr[i]<=base && i<j){
        
                    i++;
                }
                // i和j都停下了就可以交换arr[i]和arr[j]了
                int tmp=arr[i];
                arr[i]=arr[j];
                arr[j]=tmp;
            }
            //i和j相遇的时候，交换基准值和arr[i]
            arr[left]=arr[i];
            arr[i]=base;
            
            QuickSort(arr,left,i-1);  // 递归处理base的左边
            QuickSort(arr,i+1,right); // 递归处理base的右边
        }
    }

堆排序做法

import java.util.*;
    
    public class Solution {
        
        public int findKth(int[] a, int n, int K) {
        
            // write code here
            PriorityQueue<Integer> pq=new PriorityQueue<>();
            for(int i=0;i<K;i++){
        
                pq.offer(a[i]);
            }
            for(int i=K;i<n;i++){
        
                pq.offer(a[i]);
                pq.poll();
            }
            return pq.peek();
        }
    }