题解 | 查找第K大的元素

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String line = in.nextLine();
            String s = line.substring(1, line.length()-1);
            String[] arr = s.split(",", -1);
            int[] nums = new int[arr.length];
            for (int i=0; i<arr.length; i++) {
                nums[i] = Integer.valueOf(arr[i]);
            }
            int res = process(nums, 3);
            System.out.println(res);
        }
    }

    private static int process(int[] nums, int k) {
        return quickSort(nums, 0, nums.length-1, k);
    }

    private static int quickSort(int[] nums, int left, int right, int k) {
        int pivot = partition(nums, left, right);
        if (pivot == nums.length - k) {
            return nums[pivot];
        } else if (pivot < nums.length - k) { // 在右边
            return quickSort(nums, pivot+1, right, k);
        }
        return quickSort(nums, left, pivot-1, k);
    }

    private static int partition(int[] nums, int left, int right) {
        int key = left;
        int val = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= val) {
                right--;
            }
            while (left < right && nums[left] <= val) {
                left++;
            }
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }
        int tmp = nums[key];
        nums[key] = nums[left];
        nums[left] = tmp;
        return left;
    }

}