线性时间选择

线性时间选择

//线性时间选择
 
package wkx;
 
import java.io.IOException;
import java.util.Date;
import java.util.Random;
import java.util.Scanner;
 
public class Test {
 
	private static int randomPartition(int[] data, int beg, int end) {
		Random rand = new Random(new Date().getTime());
		int pos = rand.nextInt(end - beg + 1) + beg;
		System.out.println("pos=" + pos);
		int t = data[beg];
		data[beg] = data[pos];
		data[pos] = t;
 
		int key = data[beg];
		while (beg < end) {
			while (beg < end && data[end] >= key)
				end--;
			data[beg] = data[end];
			while (beg < end && data[beg] <= key)
				beg++;
			data[end] = data[beg];
		}
		data[beg] = key;
		return beg;
	}
 
	private static int select(int[] data, int beg, int end, int k) {
		if (beg == end)
			return data[beg];
		int mid = randomPartition(data, beg, end);
		int size = mid - beg + 1;
		if (k <= size)
			return select(data, beg, mid, k);
		else
			return select(data, mid + 1, end, k - size);
	}
 
	public static void main(String[] args) throws IOException {
		int[] data = new int[100];
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {
			int len = in.nextInt();
			int k = in.nextInt();
			for (int i = 0; i < len; i++)
				data[i] = in.nextInt();
			System.out.println(select(data, 0, len - 1, k));
		}
	}
 
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注