1.第K顺序统计量概念

  在一个由n个元素组成的集合中,第k个顺序统计量是该集合中第k小的元素。例如,最小值是第1顺序统计量,最大值是第n顺序统计量。

2.求Top K元素与求第K顺序统计量不同

  Top K元素:是指求数组中的最大(或者最小的)K个元素,一般K比较小,采用最大(或者最小)堆实现。之前写过的一篇有关文章是:

海量数据处理的 Top K算法(问题) 小顶堆实现

  第K顺序统计量:只求解数组中的第K大元素,是求解一个元素。一般使用“快速排序”的思想,将数组划分求解。

3.第K顺序统计量求解代码

  这是求解第K统计量代码,即第k小。如果要求第K大,可以根据数组长度转化为第n-k小。

public class TheK { 
    int array[]={12,435,123,1,345,546,12,546,7,86,354,7}; 
    int paarray(int i,int j) 
    { 
        int pivot=array[i]; //用区间的第1个记录作为基准 
        while(i<j) 
        {     //从区间两端交替向中间扫描,直至i=j为止 
            while(i<j&&array[j]>=pivot) //pivot相当于在位置i上 
                   j--;  
            if(i<j) 
                   array[i++]=array[j]; //相当于交换array[i]和array[j],交换后i指针加1 
            while(i<j&&array[i]<=pivot) //pivot相当于在位置j上 
                   i++; 
            if(i<j) 
                    array[j--]=array[i]; //相当于交换array[i]和array[j],交换后j指针减1 
        } 
        array[i]=pivot; //基准记录已被最后定位 
        return i; 
    } 
     
    void getK(int k) 
    { 
        int mid=paarray(0,array.length-1); 
        while(mid!=k) 
        { 
            if(mid<k) 
                mid=paarray(mid+1,array.length-1); 
            else 
                mid=paarray(0,mid-1); 
        } 
        System.out.println("The num of "+k+" is:"+array[k]); 
    } 
     
    public static void main(String args[]){ 
        //查找第6个元素。数组元素编号从0开始 
        new TheK().getK(6); 
    } 
}

 

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

物件捆绑 背包问题 动态规划 求解讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。