ホームページ >データベース >mysql チュートリアル >【编程之美】2.5寻找最大的k个数

【编程之美】2.5寻找最大的k个数

WBOY
WBOYオリジナル
2016-06-07 15:15:421332ブラウズ

题目: 有很多无序的数,如何从中选取最大的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  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 > 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)
            break;
        if((q <br>
<br>

<p><br>
</p>
<p><span>思路三:</span></p>
<p><span>另外一种比较受限的方法:可以利用计数排序那样,当所有的N个数都为正数并且变化范围不大的时候,我们可以设置一个数组来统计每一个数据出现的次数。然后遍历这个数组,找到最大的k个数据即可。</span></p>
<p></p><pre class="brush:php;toolbar:false">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大数据出现在哪个区域范围内。然后再对该局域进行分块处理。



声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。