题解 | #牛群中的第 k 小牛#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
     int ans=-1;
     boolean flag=false;
    public int findKthSmallest (int[] nums, int k) {
        // write code here
        kp(nums,k,0,nums.length-1);
        return ans;
    }
    void kp(int[] nums,int k,int left,int right){
        if(left>=right){
            if(left==k-1){
                ans=nums[left];
            }
            return;
        }
        int key=nums[left];
        int l=left;
        int r=right;
        while(l<r){
            while(l<r&&nums[r]>=key){
                r--;
            }
            nums[l]=nums[r];
            while(l<r&&nums[l]<=key){
                l++;
            }
            nums[r]=nums[l];
        }
        nums[l]=key;
        if(l==k-1){
            ans=nums[l];
          
        }
        if(l>k-1){
            kp(nums,k,left,l-1);
        }
        if(l<k-1){
            kp(nums,k,l+1,right);
        }
    }
}