求最大（小）k个元素的分析

简介

    求最大（小）k个元素的问题已经在很多书或者文章上进行了大量的讨论。它有多种解决办法，每一种办法有它所独特适用的一面。同时，这个问题也和求第k大（小）的元素有很紧密的关系。这里，我们以取最小k个元素为例。主要按照《编程之美》这本书上讨论的思路作了一个详细的实现。并对每一种方法作了简单的讨论。

排序方法

    这是我们所能想到的比较直接的办法。首先对所有的元素排序，然后取第k个元素。这样这个元素及之前的那些元素就是我们所需要寻找的。具体的实现我们可以考虑用到常用的几种排序方法，比如归并排序和快速排序。另外，还有一种就是采用选择排序作一点修改。

方法一、快速排序的实现

public static void quickSort(int[] a, int l, int r)
{
	if(l < r)
	{
		int q = partition(a, l, r);
		quickSort(a, l, q - 1);
		quickSort(a, q + 1, r);
	}
}

public static int partition(int[] a, int l, int r)
{
	int x = a[r];
	int i = l - 1;
	for(int j = l; j < r; j++)
	{
		if(a[j] <= x)
		{
			i++;
			swap(a, i, j);
		}
	}
	swap(a, i + 1, r);
	return i + 1;
}

public static void swap(int[] a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

     这部分主要是quicksort的实现。在通过quicksort得到结果之后。取数组中索引为k的那个元素。然后将元素从头到k的输出就可以了。这部分的伪代码实现如下：

for(int i = 0; i < k; i++)
    System.out.print(a[i] + " ");

 因为quicksort修改了原来排序的元素，只要取第k个的索引就找到结果了，结果数组是已经完全排序的。

和quicksort类似，归并排序的过程基本一样，就不赘述。这两种方法的时间复杂度为nlgn。

选择排序实现：

    我们如果注意到选择排序的算法的话，就会发现，它的过程比较符合我们这个问题的期望。因为它的过程是首先找到数组里最小的元素，然后放到数组的第一个位置，然后在剩下的元素里再找最小的，依次从前往后放。我们需要取k个最小的元素，那么按照这个要求，只要找到最小的K个元素就可以了。具体的实现如下：

public static void sort(int[] a, int k)
{
	for(int i = 0; i < k; i++)
	{
		int min = i;
		for(int j = i + 1; j < a.length; j++)
		{
			if(a[j] < a[min])
				min = j;
		}
		if(i != min)
		{
			swap(a, i, min);
		}
	}
}

public static void swap(int[] a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

     这部分代码和纯粹的selection sort的区别就在于原来的selection sort方法要在外面的循环一直遍历到倒数第二个元素，现在只需要遍历到第k个元素。这种方法的时间复杂度为n*k。和前面那种排序的方法比起来，前者为nlgn，两者的差别在于lgn和k。如果k < lgn的话，则第二种选择排序的方法更加理想。

适用场景：

    我们这里采用的都是排序的过程，比如前面的快速排序的方式，每次划分要遍历一次整个数组。采用选择排序也类似，需要从数组里挑选最小的元素。这样做就有一个限制，如果要处理的数据量很大，不能一次将所有的数据都读到内存里面来的话，这种排序的方法就不适用了。

 

方法二、借鉴快速排序的思路

    这种方法借鉴了快速排序的思路。在快速排序中，每次我们要对数组进行partition，分组的结果是使得在我们指定的元素左边的元素都小于它，在它右边的元素都大于它。那么，假设我们指定一个元素s，通过partition方法，我们可以得到划分后s所在的索引值。这个索引值假设为i，则表示元素s是集合里第i大的元素。通过和我们所期望的k比较，如果i < k，说明需要在大于s的元素里找出k - i个元素。否则，只需要在i索引的范围内继续寻找k。具体的实现代码如下：

public static int kSmall(int[] a, int start, int end, int i)
{
	int q = partition(a, start, end);
	int k = q - start + 1;
	if(i == k)
		return q;
	else if(i < k)
		return kSmall(a, start, q - 1, i);
	else
		return kSmall(a, q + 1, end, i - k);
}

public static int partition(int[] a, int l, int r)
{
	int x = a[r];
	int i = l - 1;
	for(int j = l; j < r; j++)
	{
		if(a[j] <= x)
		{
			i++;
			swap(a, i, j);
		}
	}
	swap(a, i + 1, r);
	return i + 1;
}

public static void swap(int[] a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

    我们这里用到分划的方法，每次将元素划分为一部分大于指定元素一部分小于指定元素，然后再在缩小的范围内继续调整。这种方法和我们随机分划来求第k大的元素有很类似的思路。它的时间复杂度在理想的情况下可以达到O(N)，在最坏的情况下，时间复杂度为O(N * N)。

适用场景：

    和前面的方法类似，这里的分划和调整也要每次都遍历数组元素。只是每次在分划确定了范围之后要遍历的范围缩小了。对于数据量很大的集合还是存在可能内存不够的问题。

 

方法三、借鉴二分搜索策略

    这个方法和前面的类似快速排序比较类似，不过细节稍微有点不一样。既然我们是要找第k小的元素，那么，如果我们找到最大的元素max和最小的元素min，则这个第k小的元素在这个[min, max]的区间内。我们可以用二分搜索的方法，每次取min， max的中间值，然后计算小于这个中间值的元素个数。这样就相当于求出它是第几小的元素。如果这个元素的排名比我们所期望的k小，则说明我们要在这个元素的位置以后来搜索，也就是说要在大于(min+max) / 2的值域内。

    查找小于某个值的元素个数的方法实现如下：

public static int f(int[] a, int n, int m)
{
	int count = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] <= m)
			count++;
	}
	return count;
}

 

    通过前面这么不断的调整，我们必然得到一个元素，它正好是第k小的。然后，我们再利用分划的思路，以该元素为界，将集合分成两部分。这样，这个元素及左边的部分就是所要求的结果。

查找和比对第k大元素的部分代码如下：

while(max - min > 0.5)
{
	int mid = min + (max - min) / 2;
	if(f(a, n, mid) >= k)
		max = mid - 1;
	else
		min = mid + 1;
}

   前面这部分返回一个最终的max或者min都可以。用来作为后面分划的值。 

   最后进行分划的代码如下：

public static int partial(int[] a, int l, int r, int key)
{
	int i = l - 1;
	for(int j = l; j <= r; j++)
	{
		if(a[j] <= key)
		{
			i++;
			swap(a, i, j);
		}
	}
	return i;
}

     它和partition的方法很相似，只是做了一点点的修改。因为它是要将指定的元素来进行划分，而不是partition中拿数组中最后的那个元素作为划分的标杆。中间还有一些实现求最大值和最小值的过程代码就不在这里赘述了。只是贴上一部分作为参考：

int max, min;
if(a[0] >= a[1])
{
	max = a[0];
	min = a[1];
}
else
{
	min = a[0];
	max = a[1];
}

int i;
for(i = 2; i < n; i += 2)
{
	if(i + 1 < n)
	{
		if(a[i] >= a[i + 1])
		{
			if(a[i] > max)
				max = a[i];
			if(a[i + 1] < min)
				min = a[i + 1];
		}
		else
		{
			if(a[i + 1] > max)
				max = a[i + 1];
			if(a[i] < min)
				min = a[i];
		}
	}
	else
	{
		if(a[i] > max)
			max = a[i];
		else if(a[i] < min)
			min = a[i];
	}
}

 

    总的来说，这种方法的过程如下：1. 首先找到最大最小值，时间复杂度为O(N)，更精确的说是O（3/2N）。2. 查找第K大的元素，每次需要根据折半的部分计数，每次计数的时间复杂度为O(N)。总共需要计数的次数为lgN，那么总的复杂度为NlgN。3. 根据最后的结果进行分划，这部分的时间复杂度为O(N)。所以该方法总体的时间复杂度为O(NlgN)。

适用场景：

    和我们前面的方法类似，在数据量大的时候，我们希望尽可能少的去读数据。这里却需要反复的进行查找计数，后面还要进行划分。所以在大数据量的情况下，这并不是一种理想的选择。

 

方法四、堆排序思路

    这里借鉴了堆排序的思想。我们再回顾一下堆排序里面的过程。首先包括建堆，然后每次移除最上面的元素，移除之后再进行调整。我们每次调整所需要的花费为O(lgN)。而建一个堆的时间复杂度为O(N)。在这里，假如我们要求最小的k个元素，我们可以先建立一个k个元素的最大堆。这个堆里头的根结点是k个元素最大的那个。这样，我们针对后面的每个元素和堆顶的元素比较，如果比较元素比堆顶的元素大，我们可以直接忽略，而比堆顶的元素小，我们用这个元素替换堆顶的元素并进行调整。

    有了这个思路，我们实现的代码就很好办了。以下这部分是实现建堆的部分：

public static int left(int i)
{
	return i * 2 + 1;
}

public static int right(int i)
{
	return i * 2 + 2;
}

public static void maxHeapify(int[] a, int i, int length)
{
	int l = left(i);
	int r = right(i);
	int largest = i;
	while(true)
	{
		if(l < length && a[l] > a[i])
			largest = l;
		if(r < length && a[r] > a[largest])
			largest = r;
		if(i != largest)
			swap(a, i, largest);
		else
			break;
		i = largest;
		l = left(largest);
		r = right(largest);
	}
}

public static void buildMaxHeap(int[] a)
{
	for(int i = a.length / 2; i >= 0; i--)
		maxHeapify(a, i, a.length);
}

public static void swap(int[] a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

     后面部分的实现代码如下：

for(int i = k; i < a.length; i++)
{
    if(a[i] < a[k - 1])
    {
        a[k - 1] = a[0];
        maxHeapify(a, 0, k);
    }
}

    这个方法的整体执行步骤有如下几个部分：1. 建一个k个元素大小的堆，时间复杂度为O(K)。2. 针对后面的所有元素，每次比较并调整堆。时间复杂度相当于(N - K)lgK。那么这个方法的整体时间复杂度为O(NlgK)。

适用场景：

    借鉴堆排序的过程可以说是一个比较理想的解决方法。如果k不是特别大的情况，我们可以直接在内存里建一个堆，然后每次读取一个后面的元素来比较和调整。因此对于大数据量来说，之需要读取一遍就可以实现所需要的结果。

 

方法五、借鉴计数排序

    在我前面讨论计数排序的文章里有专门提到过这种排序方法的特殊性。它要保证数据的分布在一个不是太大的范围，这样我们可以申请一个这么大范围的数组。然后在这个数组中每个元素保存对应的集合中元素出现的次数。当我们遍历整个数组得到这么一个统计结果的数组时，我们也就很容易得到第几个元素及之前元素的个数。这样再来找第k个元素就很容易了。建立这么一个统计数组的代码比较简单：

int[] c = new int[k];
for(int i = 0; i < a.length; i++)
	c[a[i]] = c[a[i]] + 1;

 后面我们来判断的代码如下：

int count = 0;
int i;
for(i = 0; i < k; i++)
{
    count += c[i];
    if(count >= k)
        break;
}
return i;

    这里是返回了i这个第k大的元素。如果要输出前面的部分就很简单了：

for(int j = 0; j < i; j++)
{
    for(int l = 0; l < c[j]; l++)
        System.out.print(j);
}

适用场景：

    这种方法采用了计数排序的思路，所以它本身就受到计数排序的两个条件限制：1. 数据分布范围不能太大。2. 数据都要大于等于0. 对于符合这种条件的大数据集合，采用这种办法排序也是一个可行的办法。 

总结

    各种求最大（小）k个元素的方法可以通过这个查找的过程取点巧。如果能找到第K小的元素并且这个元素前面所有的元素都是比该元素小的，那么我们直接在数组里输出这一个数据集合。否则，我们可以根据这个元素对所有数据做一次划分，然后取得所需要的的部分。

参考资料

编程之美

Introduction to algorithms