题目内容

  有N个整数，请找到其中最大的第K个数。

求解方法

  注意，这里题目不是topK问题，但是完全可以利用topK问题来解决。但是从算法上来说，求的是第K大的数，而计算的是前K大的数，必然是进行了额外的计算。这里给出一种基于快速排序的求解第K大数的算法。

public int findKthNum(int[] array, int left, int right, int k) {		int j = partition(array, left, right);		int target = left + k - 1;		if (j == target)			return array[j];		else if (j > target)			return findKthNum(array, left, j - 1, k);		else			return findKthNum(array, j + 1, right, k - (j - left + 1));	}	public int partition(int[] array, int left, int right) {		int j = left;		int index = getRandom(left, right);		for (int i = left; i <= right; i++) {			if (i != index && array[i] < array[index]) {				int temp = array[j];				array[j] = array[i];				array[i] = temp;				j++;			}		}		int temp = array[j];		array[j] = array[index];		array[index] = temp;		return j;	}	public int getRandom(int left, int right) {		double index = Math.random();		return (int) (index * (right - left) + left);	}复制代码