n个数字取第k大的数

 设计一组N个数，确定其中第k个最大值，方法很多，最直观的想法是将n个数由大到小排好序，取第k个数即可，但效率并不高。

 网上的方法如下：

解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。

      解法2： 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)

      解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

           1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

           2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

      解法4： 二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)

      解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)

      解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)

      解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

 

解法3：是比较好一种，用快排来做，java实现代码如下：

 

package algorithm;
/**
 * @author fengzb.fnst
 *
 */
public class N_element {

	private static int partition(int[] L, int low, int high) {
		int temp = L[low];
		int pt = L[low]; // 哨兵
		while (low != high) {
			while (low < high && L[high] <= pt)
				high--;
			L[low] = L[high];

			while (low < high && L[low] >= pt)
				low++;
			L[high] = L[low];
		}

		L[low] = temp;
		return low;
	}

	public static void quickSort(int[] L, int low, int high) // 快速排序
	{
		int pl;
		if (low < high) {
			pl = partition(L, low, high);
			quickSort(L, low, pl - 1);
			quickSort(L, pl + 1, high);
		}
	}
	
	public static void findk(int k, int[] L, int low, int high) {
		int temp;
		temp = partition(L, low, high);
		if (temp == k - 1) {
			System.out.println("第" + (temp + 1) + "大的数是:" + L[temp]);
		} else if (temp > k - 1)
			findk(k, L, low, temp - 1);
		else
			findk(k, L, temp + 1, high);

	}

	public static void main(String[] args) {
		int[] a = { 15, 25, 9, 48, 36, 100, 58, 99, 126, 5 };
		int i, k;
		System.out.println("排序前：");
		for (i = 0; i < 10; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
		k = 4;
		N_element.findk(k, a, 0, 9);
		N_element.quickSort(a, 0, 9);
		
		
		System.out.println("排序后：");

		for (i = 0; i < 10; i++) {
			System.out.print(a[i] + " ");
		}
	}
}

 

   执行结果

排序前：
15 25 9 48 36 100 58 99 126 5 
第4大的数是:58
排序后：
126 100 99 58 48 36 25 15 9 5