题解 | #第k轻的牛牛#

1. 题目考察的知识点

数组，快速排序

2. 题目解答方法的文字分析

基于快速排序，在递归操作之前判断第K大元素在哪个区间，仅对此区间进行排序

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int findKthSmallest (int[] weights, int k) {
        //题目的数组位置是从1开始算的，但我们的位置是从0开始算的，所以k要减去一。
        k=k-1;
        int low = 0,high=weights.length-1;
        //利用快速排序的分治算法进行排序，只计算答案在的那一边，答案不在的另一边则不需要排序，减少寻找k的时间。
        while(low<=high){
            int i=low ;
            //遍历数组，让小于weights[low]的在low左边，否则在右边
            for(int j=low+1;j<=high;j++){
                if(weights[j]<weights[low]){
                  swap(weights,j,++i);
                }
            }
            swap(weights,low,i);
            //通过判断k在i的哪一边，选择接下来只快速排序数组的哪一部分，节约时间
            if(k==i){
                return weights[i];
            }else if(k<i){
                high=i-1;
            }else{
                low = i+1;
            }
          
        }
        return -1;
    }
    //交换数组weights中，i和j两个位置的值
    public void swap(int[] weights,int i,int j){
         int temp= weights[j];
         weights[j]=weights[i];
         weights[i] = temp;
        
    }
}