题解 | #第k轻的牛牛#

import java.util.*;


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

    private int partation(int[] nums, int left, int right) {
        // int index = random.nextInt(right - left + 1) + left;
        int val = nums[left];
        int l = left+1, r = right;
        while(true){
            while(l <= r && nums[l] < val)l++;
            while(l <= r && nums[r] > val)r--;
            if(l >= r)break;//r是val的位置
            else{
                swap(nums, l, r);
                l++;
                r--;
            }
        }
        swap(nums,left, r);
        return r;
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}