求第k小的数

输入 n（1≤<50000001≤n<5000000 且 n 为奇数）个数字输出这些数字的第 k 小的数。最小的数是第 0小。

思路：

假设数组arr[len]

使用快速排序中的划分函数，随机查找第d小的数。如何数组第d小的数大于第k小的数，则从数组的(0,d-1)的子数组中继续划分。如何数组第d小的数小于第k小的数，则从数组的(d+1,len-1)的子数组中继续划分。直到第d小的数等于第k小的数。

代码

import java.util.Scanner;

public class Test02 {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int len=in.nextInt();
		int th=in.nextInt();
		int arr[]=new int [len];
		for(int i=0;i<arr.length;i++) {
			arr[i]=in.nextInt();
		}
		
		int num=select(arr,0,len-1,th);
		System.out.println(num);
	}

	private static int select(int[] arr, int lo, int hi, int th) {
		if (lo==hi) return arr[lo];
		int index=partition(arr,lo,hi);
		if (index==th) return arr[index];
		else if(index<th) {
			return select(arr,index+1,hi,th);
		}else if(index>th) {
			return select(arr,lo,index-1,th);
		}
		return -1;
	}

	private static int partition(int[] arr, int lo, int hi) {
		int key=arr[lo];
		int left=lo+1;
		int right=hi;
		while(true) {
			while(arr[left]<=key) {
				if (left==hi) break;
				++left;
			}
			while(key<arr[right]) {
				if (lo==right) break;
				--right;
			}
			if(left>=right) {
				break;
			}else {
				swap(arr,left,right);
			}
		}
		swap(arr,lo,right);
		return right;
	}

	private static void swap(int[] arr, int left, int right) {

		int temp=arr[left];
		arr[left]=arr[right];
		arr[right]=temp;
		
	}

	
}

5 1
4 3 2 1 5
2

以上代码提交到OJ系统中很容易得到，“Time Limit Exceeded”。Scanner类是Java中用于读取原始输入数据的便捷工具。它支持多种数据类型，并提供了正则表达式的支持，因此功能强大且易用。但是，在处理大量输入时，Scanner可能会显得相对较慢。

改进：用StreamTokenizer获取输入

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

public class Test03 {
	
	public static void main(String[] args) {
		 StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		 
		int len=nextInt(in);
		int th=nextInt(in);
		int arr[]=new int [len];
		for(int i=0;i<arr.length;i++) {
			arr[i]=nextInt(in);
		}
		
		int num=select(arr,0,len-1,th);
		System.out.println(num);
	}

	
	private static int nextInt(StreamTokenizer in)  {
		try {
			if (in.nextToken()!=StreamTokenizer.TT_EOF) {
				return (int) in.nval;
			}
		}catch(IOException e){
			System.out.println(e);
		}
		
		return 0;
	}


	private static int select(int[] arr, int lo, int hi, int th) {
		if (lo==hi) return arr[lo];
//		此时求出了第index小的数字
		int index=partition(arr,lo,hi);
		if (index==th) return arr[index];
		else if(index<th) {
			return select(arr,index+1,hi,th);
		}else if(index>th) {
			return select(arr,lo,index-1,th);
		}
		return -1;
	}

	/**
	 * 快速排序中的划分思想
	 * @param arr
	 * @param lo
	 * @param hi
	 * @return
	 */
	private static int partition(int[] arr, int lo, int hi) {
		int key=arr[lo];
		int left=lo+1;
		int right=hi;
		while(true) {
			while(arr[left]<=key) {
				if (left==hi) break;
				++left;
			}
			while(key<arr[right]) {
				if (lo==right) break;
				--right;
			}
			if(left>=right) {
				break;
			}else {
				swap(arr,left,right);
			}
		}
		swap(arr,lo,right);
		return right;
	}

	private static void swap(int[] arr, int left, int right) {

		int temp=arr[left];
		arr[left]=arr[right];
		arr[right]=temp;
		
	}

	
}