题目: 有很多无序的数,如何从中选取最大的k个数 题目解析: 之前在《程序员编程艺术》上已经遇到这样的题——最小的k个数。本质都一样。 这里再总结一下: 思路1:使用类快排的方法 选取S中一个元素作为枢纽元v,将集合S-{v}分割成S1和S2,就像快速排序那
题目:
有很多无序的数,如何从中选取最大的k个数
题目解析:
之前在《程序员编程艺术》上已经遇到这样的题——最小的k个数。本质都一样。
这里再总结一下:
思路1:使用类似快排的方法
- 选取S中一个元素作为枢纽元v,将集合S-{v}分割成S1和S2,就像快速排序那样
- 如果k
- 如果k = 1 + |S1|,那么枢纽元素就是第k个最小元素,即找到,直接返回它。
- 否则,这第k个最小元素就在S2中,即S2中的第(k - |S1| - 1)个最小元素,我们递归调用并返回QuickSelect(S2, k - |S1| - 1)。
此算法的平均运行时间为O(n)。
简化版本(三个元素中选取中间值)//QuickSelect 将第k小的元素放在 a[k-1] void QuickSelect( int a[], int k, int left, int right ) { int i, j; int pivot; if( left + cutoff pivot ){ } if( i < j ) swap( &a[ i ], &a[ j ] ); else break; } //重置枢纽元 swap( &a[ i ], &a[ right - 1 ] ); if( k i + 1 ) QuickSelect( a, k, i + 1, right ); } else InsertSort( a + left, right - left + 1 ); }
登录后复制
随机化版本:
// Random Partition int RandomInRange(int min, int max) { int random = rand() % (max - min + 1) + min; return random; } void Swap(int* num1, int* num2) { int temp = *num1; *num1 = *num2; *num2 = temp; } int Partition(int data[], int length, int start, int end) { if(data == NULL || length = length) throw new std::exception("Invalid Parameters"); int index = RandomInRange(start, end); Swap(&data[index], &data[end]); int small = start - 1; for(index = start; index < end; ++ index) { if(data[index] < data[end]) { ++ small; if(small != index) Swap(&data[index], &data[small]); } } ++ small; Swap(&data[small], &data[end]); return small; } int MoreThanHalfNum_Solution1(int* numbers, int length) { if(CheckInvalidArray(numbers, length)) return 0; int middle = length >> 1; int start = 0; int end = length - 1; int index = Partition(numbers, length, start, end); while(index != middle) { if(index > middle) { end = index - 1; index = Partition(numbers, length, start, end); } else { start = index + 1; index = Partition(numbers, length, start, end); } } int result = numbers[middle]; if(!CheckMoreThanHalf(numbers, length, result)) result = 0; return result; }
登录后复制
思路二:
堆排序的方法,只对前k个先排序,然后遍历整个序列。这样的方法特别适合大量的数据。
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 < K-1,才有后面的q+1 q = q+1; if(h[q] < h[p]){ t = h[p]; h[p] = h[q]; h[q] = t; p = q; }else break; } }
登录后复制
思路三:
另外一种比较受限的方法:可以利用计数排序那样,当所有的N个数都为正数并且变化范围不大的时候,我们可以设置一个数组来统计每一个数据出现的次数。然后遍历这个数组,找到最大的k个数据即可。
for(sumcount = 0,v = MAXN - 1;v >= 0;v--){ sumcount += count[v]; if(sumcount >= k) break; } return v;
登录后复制
拓展:
毕竟对于大数据来说,我们要让认知面更广,往往处理大数据的方法,平时一般见不到。
对于不能保证所有的数为正数,且变换范围不大,我们也可以利用思路三来分组处理:
假设N个数中最大值max,最小值min。我们可以将[min,max]分成M个区域,每个小区域跨度为(max-min)/M,然后扫描一遍所有的数据,统计各个区域包含的数据。然后找到地k大数据出现在哪个区域范围内。然后再对该局域进行分块处理。