求第k小的数（洛谷P1923题题解，Java/C++语言描述）

题目要求

题目链接

分析

《查找第K大/小元素算法》

这题不使用线性复杂度算法是过不去的（除非你用C++的[内置函数]or[快读+sort()]） Java应该是不可能过去的，你用C++可能卡在T上，Java还没到T呢，M直接卡爆了，顶多60分水平吧。

下面是Java版本，线性复杂度，尽可能优化，60分：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 线性复杂度算法
 * 该算法的C++版本可AC，但Java版本就会MLE/TLE
 * 该算法C++版本跑的比nth_element()跑得快
 */
public class Main {

    private static int[] nums;

    private static int k, num;

    private static void swap(int left, int right) {
        int temp = nums[left];
        nums[left]  = nums[right];
        nums[right] = temp;
    }

    private static void sort(int left, int right) {
        int left_mid=left, right_mid=right, mid= nums[(left+right)/2];
        while (left_mid  mid) {
                right_mid--;
            }
            while (nums[left_mid]