292011

写一段程序,找出数组中第k大小的数,输出数所在的位置。

【解法一】

我们先假设元素的数量不大,例如在几千个左右,在这种情况下,那我们就排序一下吧。在这里,快速排序或堆排序都是不错的选择,他们的平均时间复杂度都是 O(N * log2N)。然后取出前 K 个,O(K)。总时间复杂度 O(N * log2N)+ O(K) = O(N * log2N)。

你一定注意到了,当 K=1 时,上面的算法也是 O(N * log2N)的复杂度,而显然我们可以通过 N-1 次的比较和交换得到结果。上面的算法把整个数组都进行了排序,而原题目只要求最大的 K 个数,并不需要前 K 个数有序,也不需要后 N-K 个数有序。

怎么能够避免做后 N-K 个数的排序呢?我们需要部分排序的算法,选择排序和交换排序都是不错的选择。把 N 个数中的前 K 大个数排序出来,复杂度是O(N * K)。

那一个更好呢?O(N * log2N)还是 O(N * K)?
这取决于 K 的大小,这是你需要在面试者那里弄清楚的问题。在 K(K < = log2N)较小的情况下,可以选择部分排序。

在下一个解法中,会通过避免对前 K 个数排序来得到更好的性能。

【解法二】

回忆一下快速排序,快排中的每一步,都是将待排数据分做两组,其中一组的数据的任何一个数都比另一组中的任何一个大,然后再对两组分别做类似的操作,然后继续下去……

在本问题中,假设 N 个数存储在数组 S 中,我们从数组 S 中随机找出一个元素 X,把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X,Sb 中元素小于 X。

这时,有两种可能性:

1. Sa中元素的个数小于K,Sa中所有的数和Sb中最大的K-|Sa|个元素(|Sa|指Sa中元素的个数)就是数组S中最大的K个数。

2. Sa中元素的个数大于或等于K,则需要返回Sa中最大的K个元素。

这样递归下去,不断把问题分解成更小的问题,平均时间复杂度 O(N *log2K)。伪代码如下:

Kbig(S, k):
if(k <= 0):
return [ ] // 返回空数组

if(length S <= k):
return S
(Sa, Sb) = Partition(S)
return Kbig(Sa, k).Append(Kbig(Sb, k – length Sa)

Partition(S):

Sa = [] // 初始化为空数组

Sb = []
// 随机选择一个数作为分组标准,以避免特殊数据下的算法退化
// 也可以通过对整个数据进行洗牌预处理实现这个目的
// Swap(S[1], S[Random() % length S])
p = S[1]
for i in [2: length S]:
S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i])
// 将p加入较小的组, 可以避免分组失败, 也使分组更均匀,提高效率
length Sa < length Sb ? Sa.Append(p) : Sb.Append(p)
return (Sa, Sb)

【解法三】

寻找 N 个数中最大的 K 个数,本质上就是寻找最大的 K 个数中最小的那个,也就是第 K 大的数。可以使用二分搜索的策略来寻找 N 个数中的第 K 大的数。对于一个给定的数 p,可以在 O(N)的时间复杂度内找出所有不小于 p 的数。假如 N 个数中最大的数为 Vmax,最小的数为 Vmin,那么这 N 个数中的第 K 大数一定在区间[Vmin, Vmax]之间。那么,可以在这个区间内二分搜索 N 个数中的第 K大数 p。伪代码如下:

while(Vmax-Vmin > delta)
{
Vmid = Vmin + (Vmax – Vmin) * 0.5;
if(f(arr, N, Vmid) >= K)
Vmin = Vmid;
else
Vmax = Vmid;
}

伪代码中 f(arr, N, Vmid)返回数组 arr[0, …, N-1]中大于等于 Vmid 的数的个数。

上述伪代码中,delta 的取值要比所有 N 个数中的任意两个不相等的元素差值之最小值小。如果所有元素都是整数,delta 可以取值 0.5。循环运行之后,得到一个区间(Vmin, Vmax),这个区间仅包含一个元素(或者多个相等的元素)。
这个元素就是第 K 大的元素。
整个算法的时间复杂度为 O(N * log2(|Vmax – Vmin|/delta))。
由于 delta 的取值要比所有 N 个数中的任意两个不相等的元素差值之最小值小,因此时间复杂度跟数据分布相关。在数据分布平均的情况下,时间复杂度为 O(N * log2(N))。

在整数的情况下,可以从另一个角度来看这个算法。假设所有整数的大小都在[0, 2m-1]之间,也就是说所有整数在二进制中都可以用 m bit 来表示(从低位到高位,分别用 0, 1, …, m-1 标记)。我们可以先考察在二进制位的第(m-1)位,将 N 个整数按该位为 1 或者 0 分成两个部分。也就是将整数分成取值为[0, 2m-1-1]和[2m-1, 2m-1]两个区间。前一个区间中的整数第(m-1)位为 0,后一个区间中的整数第(m-1)位为 1。如果该位为 1 的整数个数 A 大于等于 K,那么,在所有该位为 1 的整数中继续寻找最大的 K 个。否则,在该位为 0 的整数中寻找最大的 K-A 个。接着考虑二进制位第(m-2)位,以此类推。思路跟上面的浮点数的情况本质上一样。

对于上面两个方法,我们都需要遍历一遍整个集合,统计在该集合中大于等于某一个数的整数有多少个。不需要做随机访问操作,如果全部数据不能载入内存,可以每次都遍历一遍文件。经过统计,更新解所在的区间之后,再遍历一次文件,把在新的区间中的元素存入新的文件。下一次操作的时候,不再需要遍历全部的元素。每次需要两次文件遍历,最坏情况下,总共需要遍历文件的次数为2 * log2(|Vmax – Vmin|/delta)。由于每次更新解所在区间之后,元素数目会减少。
当所有元素能够全部载入内存之后,就可以不再通过读写文件的方式来操作了。

此外,寻找 N 个数中的第 K 大数,是一个经典问题。理论上,这个问题存在线性算法。不过这个线性算法的常数项比较大,在实际应用中效果有时并不好。

【解法四】

我们已经得到了三个解法,不过这三个解法有个共同的地方,就是需要对数据访问多次,那么就有下一个问题,如果 N 很大呢,100 亿?(更多的情况下,是面试者问你这个问题)。这个时候数据不能全部装入内存(不过也很难说,说知道以后会不会 1T 内存比 1 斤白菜还便宜),所以要求尽可能少的遍历所有数据。

不妨设 N > K,前 K 个数中的最大 K 个数是一个退化的情况,所有 K 个数就是最大的 K 个数。如果考虑第 K+1 个数 X 呢?如果 X 比最大的 K 个数中的最小的数 Y 小,那么最大的 K 个数还是保持不变。如果 X 比 Y 大,那么最大的 K个数应该去掉 Y,而包含 X。如果用一个数组来存储最大的 K 个数,每新加入一个数 X,就扫描一遍数组,得到数组中最小的数 Y。用 X 替代 Y,或者保持原数组不变。这样的方法,所耗费的时间为 O(N * K)。

进一步,可以用容量为 K 的最小堆来存储最大的 K 个数。最小堆的堆顶元素就是最大 K 个数中最小的一个。每次新考虑一个数 X,如果 X 比堆顶的元素Y 小,则不需要改变原来的堆,因为这个元素比最大的 K 个数小。如果 X 比堆顶元素大,那么用 X 替换堆顶的元素 Y。在 X 替换堆顶元素 Y 之后,X 可能破坏最小堆的结构(每个结点都比它的父亲结点大),需要更新堆来维持堆的性质。更新过程花费的时间复杂度为 O(log2K)。

 编程之美

图 2-1 是一个堆,用一个数组 h[]表示。每个元素 h[i],它的父亲结点是 h[i/2],儿子结点是 h[2 * i + 1]和 h[2 * i + 2]。每新考虑一个数 X,需要进行的更新操作伪代码如下:

if(X > h[0])
{
h[0] = X;
p = 0;
while(p < K)
{
q = 2 * p + 1;
if(q >= K)
break;
if((q < K-1) && (h[q + 1] < h[q]))
q = q + 1;
if(h[q] < h[p])
{
t = h[p];
h[p] = h[q];
h[q] = t;
p = q;
}
else
break;
}
}

因此,算法只需要扫描所有的数据一次,时间复杂度为 O(N * log2K)。这实际上是部分执行了堆排序的算法。在空间方面,由于这个算法只扫描所有的数据一次,因此我们只需要存储一个容量为 K 的堆。大多数情况下,堆可以全部载入内存。如果 K 仍然很大,我们可以尝试先找最大的 K’个元素,然后找第 K’+1个到第 2 * K’个元素,如此类推(其中容量 K’的堆可以完全载入内存)。不过这样,我们需要扫描所有数据 ceil1(K/K’)次。

【解法五】

上面类快速排序的方法平均时间复杂度是线性的。能否有确定的线性算法呢?是否可以通过改进计数排序、基数排序等来得到一个更高效的算法呢?答案是肯定的。但算法的适用范围会受到一定的限制。

如果所有 N 个数都是正整数,且它们的取值范围不太大,可以考虑申请空间,记录每个整数出现的次数,然后再从大到小取最大的 K 个。比如,所有整数都在(0, MAXN)区间中的话,利用一个数组 count[MAXN]来记录每个整数出现的个数(count[i]表示整数 i 在所有整数中出现的个数)。我们只需要扫描一遍就可以得到 count 数组。然后,寻找第 K 大的元素:

for(sumCount = 0, v = MAXN-1; v >= 0; v–)
{
sumCount += count[v];
if(sumCount >= K)
break;
}
return v;

极端情况下,如果 N 个整数各不相同,我们甚至只需要一个 bit 来存储这个整数是否存在。

参考链接:http://yilee.info/find-the-largest-k-figures-in-the-beauty-of-programming.html

相关日志

Leave a Reply

(required)

(required)

click to change(必须)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Protected by WP Anti Spam
© 2009 - 2018 冰河的博客