求第k大数

发布时间：2020-12-14 01:56:53 所属栏目：大数据来源：网络整理

导读：问题描述：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k大的元素，（这里给定的线性集是无序的）。其实这个问题很简单，直接对线性序列集qsort，再找出第k个即可。但是这样的时间复杂度就是qsort的时间复杂度O(nlogn)。有没有更快

问题描述：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k大的元素，（这里给定的线性集是无序的）。

　　其实这个问题很简单，直接对线性序列集qsort，再找出第k个即可。但是这样的时间复杂度就是qsort的时间复杂度O(nlogn)。有没有更快的方法呢？看到网上有一种解法是采取了快排的思路，但是稍微坐了些改动，然后时间复杂度能够接近O(n)。因为最近刚刚写了快排的实现，所以在这我就再把这个实现一次吧。

　　解题思路：与快排不同的是，这里只对划分出来的其中一组进行递归处理。任意选定一个pivotIndex，pivotValue = arr[pivotIndex]。经过一次划分后，pivotValue存储在storeIndex的位置，storeIndex把数组划分为两部分。比pivoteValue大的在前面，比pivotValue小的存储在后面（此时前后两部分是没有排好序的）。那么storeIndex位置的pivotValue就肯定是第storeIndex大的数。然后用K于storeIndex比较，如果K<storeIndex,那么说明第K大一定在右边，那么再对右边进行划分即可。如果K>storeIndex,那么说明第K大一定在左边，那么再对左边进行划分。然后递归，最后就可以得到第K大。

   按 Ctrl+C 复制代码 
 
 #include <stdio.h> 
 
 void swap(int *a,int *b) 
 
 { 
 
 ? ? int tmp; 
 
 ? ? tmp = *a; 
 
 ? ? *a = *b; 
 
 ? ? *b = tmp; 
 
 } 
 
 int partition(int arr[],int left,int right,int pivotIndex) 
 
 { 
 
 ? ? int storeIndex = left; 
 
 ? ? int pivotValue = arr[pivotIndex]; 
 
 ? ? int i; 
 
 ? ? swap(&arr[pivotIndex],&arr[right]); 
 
 ? ?? 
 
 ? ? for (i = left; i < right; i ++) 
 
 ? ? { 
 
 ? ? ? ? if (arr[i] > pivotValue) 
 
 ? ? ? ? { 
 
 ? ? ? ? ? ? swap(&arr[i],&arr[storeIndex]); 
 
 ? ? ? ? ? ? storeIndex++; 
 
 ? ? ? ? } 
 
 ? ? } 
 
 ? ? swap(&arr[storeIndex],&arr[right]); 
 
 ? ? return storeIndex; 
 
 } 
 
 int findKMax(int arr[],int k) 
 
 { 
 
 ? ? int nRet; 
 
 ? ? int pivotIndex = left + 1; 
 
 ? ? nRet = partition(arr,left,right,pivotIndex); 
 
 ? ? if (nRet < k) 
 
 ? ? { 
 
 ? ? ? ? return findKMax(arr,nRet+1,k); 
 
 ? ? } 
 
 ? ? else if (nRet > k) 
 
 ? ? { 
 
 ? ? ? ? return findKMax(arr,nRet-1,k); 
 
 ? ? } 
 
 ? ? ? ?? 
 
 ? ? return nRet; 
 
 } 
 
 int main() 
 
 { 
 
 ? ? int i,k,nRet; 
 
 ? ? int arr[] = {8,3,4,1,9,7,6,10}; 
 
 ? ? scanf("%d",&k); 
 
 ? ? nRet = findKMax(arr,k-1); 
 
 ? ?? 
 
 ? ? printf("The Kth Max Number locate in %d is :%dn",nRet,arr[nRet]); 
 
 ? ? for (i = 0; i < 8; i++) 
 
 ? ? { 
 
 ? ? ? ? printf("%3d",arr[i]); 
 
 ? ? } 
 
 ? ? return 0; 
 
 }? 
 
 ? 
 
   按 Ctrl+C 复制代码

　　萧萧空间列出了很多种寻找第K大数的算法。

第二次实现该算法：

复制代码

#include <stdio.h>

void swap(int arr[],int i,255); line-height:1.5!important">int j)
{
    int tmp;

    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

int partition(int left,255); line-height:1.5!important">int right)
{
    int value = arr[left];
    int p_insert,p_cmp;

    swap(arr,right);
    p_insert = p_cmp = left;

    while (p_cmp < right)
    {
        if (arr[p_cmp] < value)
        {
            swap(arr,p_insert,p_cmp);
            p_insert++;
        }
        p_cmp++;
    }
    swap(arr,right);

    return p_insert;
}

void max_k(int right,255); line-height:1.5!important">int k)
{
    int ret = partition(arr,right);
    if (ret == k) return;
    else if (ret < k)
        ret = partition(arr,ret+1,255); line-height:1.5!important">else
        ret = partition(arr,ret);     
}

int main()
{
    int arr[] = {9,10,128); line-height:1.5!important">7,128); line-height:1.5!important">8,128); line-height:1.5!important">3,128); line-height:1.5!important">12,128); line-height:1.5!important">15,128); line-height:1.5!important">76,128); line-height:1.5!important">6};
    5;

    max_k(arr,0,128); line-height:1.5!important">8,k);

    for (i = 0; i < k; i++)
    {
        printf("%d ",arr[i]);
    }
    printf(n");


    return 0;
}

2013/10/21  22:42

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!